PRELIMINARYPRELIMINARY The Personal Paper Cipher
Secure conversion of domain names into passwords.
THE PROBLEM:  Web sites that require us to login and authenticate
our identities cannot be trusted to keep our passwords secret. This
makes password reuse at multiple sites extremely unsafe:  If one site
leaks our name, eMail address and password to a hacker they attempt
to reuse that authentication to impersonate us on other sites.
Or, as the infamous Lulz Security hacking group, “LulzSec”, tweeted at
10:34am, Friday, June 24th, 2011, phrasing it somewhat less delicately:
@LulzSec: Reusing passwords is kind of like owning
multiple houses and using the same key for each one.
Don't expect people not to steal your shit.
Fri 24 Jun 10:34 via web (received via TweetDeck)
Until an industry-wide, coherent identity authentication solution is
established, the responsibility for creating a potentially limitless
number of separate website “identities” rests with each individual.

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.

For these reasons, among others, many users
refuse to centralize their password management.

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:

ppc-0

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.

What would such a system look like?
What would its requirements be?

Here were my requirements:

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:

ls1

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.

LATIN SQUARES
Although knowledge of squares having this special property of “exactly one of each character in each row and column” extends as far back into history as medieval Islam, their systematic analysis was not undertaken until 1779, by the Swiss mathematician and physicist Leonhard Euler (pronounced: “Oiler”). Euler dubbed such grids “Latin Squares” because he used Latin language characters to populate their cells. Amazingly, the fascinating properties of Latin Squares have occupied mathematicians ever since, and continue to, today. For example, even today we only know how many different Latin Square configurations can be made from grids up to 11x11. No one knows how many Latin Square configurations can be made from a grid of 12x12 or larger!
GRC's Latin Squares Workbench
lsw
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:

ls1
Note that for illustration purposes we are using a reduced
size 11 by 11 Latin Square, containing only 11 of the 26
lowercase characters of the English alphabet. The actual
Personal Paper Cipher uses a full size 26 by 26 grid.

The key principle of the Personal Paper Cipher is that a 26x26 Latin
Square, containing the 26 characters of the lowercase English alphabet,
can be used to direct a unique path through the Square, where that
path is determined by the Latin Square's specific configuration.
Phase 1: Trace a path to the Phase 2 starting point

ls3aThe 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.

Phase 2: Trace another path while outputting characters

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

ls5

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:

ls6

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:

ls6

Thus “ amazon ” enciphers to “ )rP-?JD0:/7t

And “ amazon ” will encipher to “ )rP-?JD0:/7t ” every time you
do it
using the same Personal Paper Cipher grid as your guide.

Practical Refinements & Characteristics of this Cipher

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.
Security Analysis
That's what I have for now, gang. This was taking so long that I didn't want to make everyone wait any longer. And now I want to change the whole "Phase One" path tracing to simply use the last two characters of the domain name. But this gives you a complete picture of the concept that I had — of wanting to develop a sufficiently secure paper-based domain name enciphering system — and how Latin Squares figure into the solution.

I look forward to any and all discussion this generates over in grc.thinktank!

Jump to top of page
Gibson Research Corporation is owned and operated by Steve Gibson.  The contents
of this page are Copyright (c) 2022 Gibson Research Corporation. SpinRite, ShieldsUP,
NanoProbe, and any other indicated trademarks are registered trademarks of Gibson
Research Corporation, Laguna Hills, CA, USA. GRC's web and customer privacy policy.
Jump to top of page

Last Edit: Jun 28, 2011 at 16:28 (4,169.39 days ago)Viewed 1 times per day