What We Need:
We need to somehow arrange to use a different, strong, secure and complex password for each site that requires us to invent an identity so that we can reauthenticate our identity upon our subsequent return.

Security conscious users know that passwords need to be complex and long to be safe. And GRC's Password Haystacks password padding approach offers one solution in this battle to construct secure and memorable passwords. But the trouble is, we need to create a potentially unlimited number of unique passwords. It's one thing to create and memorize and/or record a strong and unique password where we have to, for our most important sites, such as banking and eCommerce. But today we're asked to create passwords even for “throwaway” sites we may never return to, just to post some feedback in a forum of blog. And if we do return, what was that password we created the last time?

The problem has been so intractable and pervasive that many highly useful solutions, such as LastPass, KeePass, and SuperGenPass have been created to lift some of the password management burden from overwhelmed users. But all of these solutions also have liabilities. In mid 2011, LastPass users had a scare when it was revealed that some of its users' database may have escaped LastPass' control. It's convenient to have all of our authentication information stored “in the cloud” . . . but only so long as it is never stolen.

The other concern with cloud-based storage is availability. It's convenient as long as the service is available. Also in mid 2011, the United States FBI (Federal Bureau of Investigation) confiscated three racks worth of web servers, reportedly because they could not be bothered to determine which single server among them was believed to be violating the law. In the process, several score of unrelated web sites disappeared from the Internet. We would not be happy if the password manager we depend upon was among them.

Faced with these many, and growing, problems . . . a new solution was needed.

Immediately after finishing the work on the Password Haystacks password padding approach, I wanted to look in a different direction. My idea was to see whether I could design a secure cryptographic “paper cipher” requiring, for its use, no instrumentality, no technology, no computers, no software, no wires — only a simple piece of paper of some kind. A computer would certainly be required to design and print any instance of the Cipher. But once that was done, no computer would be required to use it.

This is the core of the idea I started with:

The idea of using a computer to encrypt a domain name to create a per-domain password is not new. That's the idea underlying SuperGenPass and others. Its obvious benefit is that instead of needing to record, store, or memorize random passwords that we invent per domain — with the potential problems that invites — we employ an algorithm of some sort to create — and recreate in the future — domain-name-based passwords. Then we don't need to record, store, or memorize them because we can simply recreate the same password from the same domain name any time it's needed. It's a great idea with no obvious drawbacks . . . except that all available solutions are “online” and suffer from the potential of worrisome privacy and security breach problems.

Here were my requirements:

• Easy to use
  I wasn't doing this as an intellectual curiosity. My absolute goal was to create a solution that anyone interested in creating secure passwords could learn to use quickly, and would then find to be useful and fun to use.
• Secure
  The system's security was, of course, as crucial as ease of use. This new system needed to be at least as secure as anything and everything it was replacing so that users could be confident that they were generating passwords that could not be “reverse engineered” to learn anything that might render the system less than absolutely secure. And by assisting its users to create much more secure passwords than they were normally likely to, it would be proactively increasing their security.

  What  EXACTLY  do we mean by “high security”?

  	The output encrypted passwords must be long enough to thwart brute force attacks. The Personal Paper Cipher (PPC) expands every case-insensitive input character (a-z) into a pair of pseudo-randomly chosen characters from a large and user-definable character set. Six input characters are therefore expanded into 12 output characters: A very short domain name such as “grc” can be enciphered as “grccom” – skipping the joining dot (.) – to obtain six input characters. And, as we'll see, even shorter domain names can also be expanded into 12 enciphered characters.
  	The enciphered output depends upon ALL input characters. This is an important property for high security. A minimal change to the input must result in a maximum and unpredictable change in the enciphered output. In the two examples below – which were generated by the PPC system – only the first and the last character was changed in the domain name “amazon”:
  	Every user's enciphered output is completely different from that of every other. When any user enciphers a domain name — even the same domain name — using their own Personal Paper Cipher, they will obtain a completely unique result from any other user:
  	Disclosure of SOME domain names and enciphered passwords must NOT compromise the security of ANY other passwords. Even if an attacker knew that you were generating your passwords with the PPC system — and that is not obvious from its output — and if an attacker were to somehow acquire some of your passwords generated by the PPC, it is imperative that so little about your Personal Cipher could be determined that none of your other passwords would be weakened. As we will see below, the Personal Paper Cipher achieves this by embedding a large amount of “entropy” (randomly determined data) into each instance of a user's Cipher.
  	Resistance to “computational” attack. Today's computer hobbyists (and attackers) have access to phenomenal computing power thanks to the awesome power built into modern PC graphics processing units (GPUs). The Personal Paper Cipher resists computational attacks by drawing upon a large “pool of entropy” that is unknown to attackers. Its design significantly obscures each Cipher instance's configuration details even when the operation of the PPC system itself is known.
  	Everything about the Cipher can be fully disclosed. The design of the Personal Paper Cipher is compliant with Kerckhoff's Principle, which states that: “The security of a cryptosystem must not be dependent upon the nondisclosure of the algorithm; it should only depend upon the nondisclosure of the key.” Everything about the design and operation of the PPC is disclosed here. Nothing is kept secret. Yet attackers gain nothing that might help them to crack any user's password sets.

• Compatible
  If the Cipher produced a password that a website could not accept we'd be in trouble. When we make one up, we just adapt what we've made up to the website's rules and store the result. But the Personal Paper Cipher system's goal is to free us of having to remember anything. We solve this by allowing the user to freely choose the range of characters produced by the Cipher. Our recommendation (unlike the somewhat extreme examples above) is to restrict the Cipher's output to upper and lowercase alphabetic characters plus numeric digits. While that doesn't provide as much security as using special characters, this provides compatibility with sites that do not allow special characters, and padding with special characters can be easily, and memorably added, if desired and permitted. (And note that any other password generator would face the same limitations.)
• Variable security
  Today's websites have differing rules for password length. For reasons of their own, some sites place lower and/or upper limits on the lengths of the passwords they will accept. So any robust password ciphering system should be able to generate domain-name-based password strings of any length. The Personal Paper Cipher can.
• Flexible & powerful
  A flexible password generating system should be able, when needed, to generate “alternate” passwords for a given domain name. This might be useful if the primary password is compromised, or if a site requires its passwords to be changed periodically. A system that cannot generate alternate passwords on demand would prove too limited. The PPC readily produces up to 52 unique passwords for every domain name.
• Everlasting & future proof
  Technology moves at a rapid pace, often obsoleting older technologies. How many people are still able to play 33 RPM vinyl record albums or 8-track tapes with the equipment they have in their homes or in their cars? Sometimes a solution that does not depend upon technology is superior because you'll never find yourself unable to “play” it. Being a carefully constructed piece of paper, the PPC system can be used fifty years from now if we're stuck using passwords until then.
• Utterly reliable
  The Personal Paper Cipher system requires no instrumentality, uses no power, no batteries, no computers. It cannot be rendered obsolete by some future upgrade. You won't be without it if a web browser upgrade no longer supports its earlier plug-ins, or if the company providing a free service starts charging for it, or is acquired by another company. It's yours forever. There's nothing to break.
• Universal
  Since the PPC can encipher ANY textual input into a deterministic string of encrypted output, which can be readily recreated at any future time, it can be used for many other purposes. For example, if a file must be encrypted with a secret key known only to the sender and receiver, both parties could have an identical instance of the Personal Paper Cipher for this purpose. The sender encrypts a (plaintext) string of six to eight characters, which is then used as the key to encrypt the file. The user sends the file along with the plaintext string in the clear without concern of eavesdroppers. Only the recipient with the same instance of the Personal Paper Cipher can take the plaintext string and encipher it into the same key to decrypt the file.

Here's How It Works

In order to support several of its important security features, such as its ability to have all characters of the input affect all characters of the output, the Personal Paper Cipher must have memory: It's future must be affected by its past. In computer jargon we would say that it must be “stateful” or be able to “save state”. It has a finite number of states. In fact, it has exactly 676. In computer jargon the Personal Paper Cipher would be described as: a finite state machine. Here's what that means:

Consider this grid containing lowercase alphabetic characters:

Even after studying it for some time it probably looks rather random. It actually IS very random (which is a good thing for us), but it was also very deliberately and carefully designed. It has exactly ONE very important property. Can you see what it is? If you have a theory, or if you give up, click the button below to add some highlighting to just the 'a' characters and study their relationship.

Do you see what's so special?  What's very special about the grid of characters above, is that EVERY character, not just the 'a's, appears exactly ONCE in every row and column of the grid. This special grid organization is called a Latin Square and it lies at the heart of the operation of the Personal Paper Cipher. In computer jargon we would say that the Personal Paper Cipher is a finite state machine driven by a Latin Square.

GRC's Latin Squares Workbench

During the early development of the Personal Paper Cipher, we needed to develop, prove, and demonstrate a number of theories of Latin Square manipulation. To aid in this research we created an interactive “Latin Squares Workbench” which allows for the comfortable manipulation and experimentation with Latin Squares ranging in sizes from 3x3 to 6x6. You are invited to experiment with these intriguing mathematical constructions which have fascinated mathematicians for centuries.

Why do Latin Squares matter? . . .   Because they allow us to do this:

The Personal Paper Cipher employs two “Phases” for the encryption of a domain name into a secure domain-specific password: The first phase determines the starting point for the second phase by tracing the domain name's characters through the Grid, as shown to the left and (larger) above. Once the first phase has determined the starting point, the second phase emits the enciphered password characters.

As shown in the diagram, each step alternates between following a column or a row. Although you could start from any of the Grid's 26 columns, or any of the Grid's 26 rows, the most important consideration is consistency. So choose a method and stick to it, otherwise you will obtain completely different results from one time to the next. But, at the same time, this flexibility can come in very handy. If you should need to generate alternate passwords for the same domain (such as when a domain's password policies require that passwords are changed), a total of 26+26, or 52, are readily available simply by starting in a different row or column. The general rule for standard PPC operation is to start along the top row, locating the first character of the domain's name there and then finding the domain's second character in the column below.

The second phase of the encryption process is very similar to the first, with a few additions:

First, as shown in the simplified diagram above, the second phase path BEGINS where the first phase path ends. In other words, the path traced during the first phase is used to determine the starting point for the second phase. The row or column where the phase one path ends is the location where the first character of the domain name is found to begin the second phase's path.

In order to output encrypted characters, the grid is expanded to contain a large assortment of randomly chosen output characters:

In the sample grid above, the original Latin Square grid characters are colored blue with a green background to clearly distinguish them from the grid's output characters to make them clear during path following. You will also notice that the red “output characters” surround each blue/green Latin Square character on each side.

As shown by the diagram below, the encrypted domain name is obtained by recording the (red) output characters to the left and right of each of the domain name's first six characters while following the Phase 2 path:

A three-point summary to set the stage:

1. The Personal Paper Cipher consists of a 26x26 Latin Square containing the lowercase English alphabet. The Latin Square's columns are separated by columns of randomly-chosen characters from the output character set. Adjacent Latin Square columns share the column of output characters that lie between them.
2. The domain name to be enciphered is first traced through the Square by starting at a known location — usually along the top row — then looking up successive characters of the domain name while alternating between rows and columns.
3. Once the end of the first path has been reached, the process is repeated. But this time the path being traced begins at the previous path's ending location and, as each character from the domain name is reached, the randomly-chosen output characters appearing to each side of the Latin Square's character is recorded.

• The Cipher generates two output characters for every character of domain name.
  The Password Haystacks brute-force cracking estimator teaches us that a password needs to have at least twelve (12) characters to be sufficiently safe and future proof. But many of the most popular and desirable domains have fewer characters since they are easier to remember and type. So the Cipher was designed to expand every input character into two output characters.
• The input character set:
  The input character set, which appears in the Latin Square columns, is all lowercase alphabetic because domain names are insensitive to alphabetic case. The non-alphabetic characters that are also valid in domain names (the digits 0-9, the period (.) and hyphen (-) ) do not appear on the Latin Square and are skipped whenever they are encountered.
• The output character set:
  The output character set, being chosen by what is essentially a look-up algorithm and table, is completely flexible and may be tailored to fit the user's needs. Although the examples above show extensive use of special characters, since many websites are hostile to special characters, practical recommendation is to generate your Personal Paper Cipher using only upper and lowercase alphabetic and digits, with an accentuated distribution of digits. Then, in following the convention illustrated by the Password Haystacks estimator, add your own special character(s) to the resulting password for all sites that allow the use of special characters. In this fashion the PPC system can be used to generate a highly-compatible alphanumeric-only root passcode, which you can then strengthen further with the optional addition of one or more special characters. And if a site refuses to allow special characters, simply omit them.
• The phase 1 path length
  The initial phase 1 path tracing is performed to greatly enhance the Cipher's security. Consider the two domain names “amazon.com” and “amazing.com” which both share the same first four characters: “amaz”. Suppose that you were not “warming up” the Cipher by first tracing a phase 1 path. In that case, every website whose first domain name character was 'a' would always encipher to the same first two password characters. And any websites whose domain names both began with 'am' would always encipher to the same first four password characters, and so forth. So in the case of “amazon.com” and “amazing.com”, if a theoretical attacker knew that you were using the Personal Paper Cipher, and if they had also compromised your account on the “amazing.com” web site to obtain your PPC-generated password there, then this attacker would also have the first eight characters of your PPC-generated password for “amazon.com” . . . making it significant easier to brute-force the remaining characters. But using a phase 1 warm up defeats this theoretical attack by changing the starting point for the phase 2 encryption, making it dependent upon the enough of the domain name characters to assure that different enipherings are generated for similar domain names.

  So this brings us back to the topic of this point: The phase 1 path length. Now that we've seen what the phase 1 path tracing accomplishes — helping domain names with similar beginnings to encipher differently — you can decide how you want to handle it. The only requirement is that you establish a rule and stick with it. Tracing the entire path for the domain “allthingsconsidered.com” would be extremely tedious and error prone. And it's really unnecessary overkill.

  The rule-of-thumb we recommend is to trace up to the top level domain separating dot (.), but never more than six characters. So the path for “grc.com” would be traced for “grc” only, and the path for “allthingsconsidered.com” would stop after “allthi” since that's almost certainly sufficient.

Finally, since the only reason for the initial cipher warm up is to prevent the same initial characters from always generating the same ...

Gang... (from GRC's newsgroups): In thinking this through while writing it up, I have changed my mind about the best way to handle the initialization phase. The point of the initialization is to find a variable but domain-based starting point. It has probably occurred to you guys that the process of tracing a path is akin to hashing, since all characters are mixed and together determine the result, and the process loses information and cannot be reversed. But, in the end, no matter how long a path we follow, we're only selecting from among one of 26 rows or 26 columns — depending upon the parity of the path's length. Following a longer path does have the advantage of removing any frequency distribution bias, so that's somewhat useful. But I don't think that starting the trace at the beginning of the domain name makes the most sense. For example: If we were only to perform a two-character phase 1 warm up, then it would provide ineffective scrambling between any domains beginning with the same first two characters. It makes much more sense, I think, to pick one or more characters that are likely to be different from the characters at the beginning of the domain name. Since any path hashing always distills to one of just 26 rows or columns, it's tempting to ignore path hashing and just choose the last character of the primary domain name (before the TLD separating dot) as the starting column for the enciphering phase. That's very clean and very simple. Much simpler in fact. But if the frequency distribution of last characters was highly skewed, as it likely is, then many columns would be under represented and others would be over represented. So perhaps use the final two characters of the domain name to obtain the enciphering starting point. The second to the last character, found along the top row picks the column, and the last character picks the starting row... and the encipering begins along that row. So the starting ROW, one of the 26 possible, is dependent upon the final two characters of the domain name instead of the beginning characters, which would tend to be duplicative.

(This improvement, which I like the more I think about it, will necessitate changing a bunch of the language and graphics above, but I didn't want to delay sharing this page with the newsgroup gang any longer. So I'm only documenting it here for the moment  . . . but I will reflect those changed from here on below.)

• The enciphering length (is entirely up to you)
  Our Password Haystacks brute force password cracking estimator shows that there are 5.19x10²⁵ combinations of 12 alphanumeric characters plus one special character, or 1.26x10²⁵ combinations of 14 alphanumeric characters without any special characters added. In other words, although special characters are a powerful addition, adding another pair of randomly chosen alphanumeric-only characters is nearly as strong and, if you check with the Haystack Calculator, plenty strong. So you might choose to use the first 7 characters of a domain name (rather than 6) to generate a 14 character password (rather than 12), which would be 3,844 times more difficult to crack. Or you could use 8! it's really up to you.
• Short domain names (like grc.com)
  There is no security weakness created by continuing to encipher some or all of the “com”, “net”, “org”, etc. at the end of a short domain name like “grc.com”. So you can simply omit the separating dot and trace the path into the top-level domain name. If, even then, you run out of domain name before you have enciphered enough characters to fulfill your own password length policy, you can simply start over from the beginning of the name until you have sufficient characters. Since there is only a 1.923% chance that reused characters from the beginning of the domain name will encipher to the same output characters, so this is a useful and strong solution for ultra-short domain names.
• Duplicate domain name characters (as in zoo.com)
  Duplicated domain name characters produce duplicated output characters. This weakens the resulting password by making two of its characters redundant and predictable to an attacker who knew you were using this system. So the best policy is to simply skip over the second character of a duplicate much like you skip over digits and punctuation.
• Flexibility vs consistency
  As we mentioned above, the Personal Paper Cipher system can be used in many ways. This makes it quite flexible and powerful. If you needed a second different password for the same domain name, you could start alnog the left edge column rather than the top row. Or you could start on the second row instead of the first. Or to determine your starting point you could use the last two characters in opposite order, etc. But since the goal is usually to be able to recreate a previously enciphered result, being consistent with your use of the PPC grid is important.

How many steps should you take?
If you were using the PPC system to encipher a very long domain name such as “allthingsconsidered.com” the task of following that name's entire path to the end would quickly become quite tedious and prone to error. It is also unnecessary for the security of the Personal Paper Cipher.

As we'll see next, the system's Phase 2 (enciphering) begins at the location determined by the initial Phase 1 path following.

The first question that arises is:  How secure is this?

As we will see below, only a portion of the Personal Paper Cipher's security comes from the attacker's ignorance of the configuration of the Latin Square we are using. But it does raise the question: could an attacker guess or computationally “brute force” the configuration of the particular Square we are using?

The Cipher's design actively prevents the disclosure of any particular Square, so the feasibility of guessing or brute forcing a Square's configuration, assuming the absence of any other clues, is primarily determined by the total number of possible Latin Squares from among which ours was chosen. As was mentioned in the “Latin Squares” box above, mathematicians who have studied Latin Squares have only been able to obtain an exact count for Squares having sizes up to 11x11 (and the exact count for 11x11 Squares was only recently obtained.) What the math gurus have been able to state with certainty, is that the lower bound on the number of Latin Squares, of a given size 'n' by 'n' is given by the equation shown on the left. In other words, although no one knows exactly how many specific Latin Square configurations there are of any size larger than 11x11 (because there are too many!), we do know that there are at least as many as specified by that equation. But how many is that?

Plugging the number (n=26) into the lower bound equation for the Personal Paper Cipher's 26x26 Latin Square results in a number so large as to be rather ridiculous. It is: 9 336 974 347 720 076 203 095 381 302 683 075 484 706 012 030 875 383 265 106 777 232 515 384 291 786 329 470 875 840 456 766 821 029 030 235 438 914 174 291 844 167 774 650 650 291 329 460 401 751 489 013 555 810 781 700 163 431 985 765 122 298 613 958 200 230 192 236 631 943 316 085 768 502 914 719 815 963 609 471 283 139 690 899 669 496 766 419 404 467 151 772 248 428 431 825 394 305 641 480 706 711 487 437 686 906 450 684 680 968 293 622 304 401 609 062 321 217 193 606 241 756 724 745 170 796 786 016 394 203 303 300 168 583 550 145 590 123 023 289 449 057 087

This number, expressed in scientific notation, is: 9.337 x 10⁴²⁶ and the log(2) (logarithm base 2) is approximately 1418. This means that a binary number having at least 1418 bits (because this is the known lower bound) would be required to specify one of the 26x26 Latin Squares possible.

During the development of this Personal Paper Cipher system, we developed several different algorithms that randomly found one single Latin Square from among all of those that are possible. However, to assure TNO (trust no one) style privacy, this code must run as JavaScript on the user's own web browser (that way no one, not even GRC, has any idea what your individual Cipher Square looks like). The solutions we developed did allow for highly efficient client-side JavaScript implementation, but sometimes the search took so long that browser warning messages popped up, and some users have older and much slower systems. In the end we chose a secure compromise that allows us to quickly choose one Latin Square from among a smaller, but still massive subset of all possible Squares.

The final algorithm for Latin Square generation used by the PPC system randomly selects one Latin Square from among a subset containing 26!² x 25! x 6 Squares. This is 15 136 831 721 341 031 145 555 109 377 300 868 031 260 208 035 408 929 173 274 624 000 000 000 000 000 000; in scientific notation: 1.513 x 10⁷⁹, or 263 bits of effective entropy — and security. And, as we'll see below, this is only one of several places from which the PPC system obtains its security.

Getting back to how it works . . .