[ale] OT - New encryption technology using a piece of paper

[Michael Trausch]

On 09/03/2011 10:45 AM, Ron Frazier wrote:
> Hi guys,
> 
> I just finished listening to episode 315 of Steve Gibson's Security Now 
> podcast. He's invented a new encryption system that works using just a 
> piece of paper (once the piece of paper is created). He uses a specially 
> designed character grid modeled after Latin Squares (don't ask me what 
> that is) which allows you to encrypt passwords for each website you 
> visit using just the piece of paper. I haven't had any time to study the 
> method, but I thought it was interesting so I'm passing it along. Here 
> is a quote from his website:
> 
> quote on -->
> 
> This “Off The Grid” technology is the only known system to provide
> 
> secure encryption using nothing but a specially designed piece of paper.
> 
> Although this system initially uses software to design and print the 
> grid, no technology of any kind is used to perform the encryption. Every 
> other strong and modern encryption technology relies upon software 
> running in your computer, your browser, your phone, or some other device 
> to encrypt, decrypt, or store your passwords. And as everyone knows, any 
> software-based system can be compromised by malware . . . and sooner or 
> later, most are.
> 
> <-- quote off

As can nearly always be proved, security relies not only on the
competency of the people running systems and services, but that of the
end user.  And perhaps just as importantly, _any_ system that aims to
provide useful security must not sacrifice a significant amount of
convenience.

This system is, from the very outset, not very difficult to use.  But it
is time-consuming in that the human is very error-prone, and humans can
not be relied upon to perfectly follow the steps to any algorithm with
efficiency.  But that's just the start.

He shows an example on his site where he creates a password using
"amazon" as the input, presumably for amazon.com.  The resulting
password that he came up with was "gcznegmacmzg".  This is a horrible
password.  And the "full scale" grid uses only 52 possible characters
for output; that is, upper and lower case letters.

Now, let's assume for a moment that the password is being used with a
service that actually does things (mostly) right and stores only salted,
hashed passwords (to do things completely correctly, they should have a
mandatory KDF that runs for at least 25,000 rounds, but given that most
people are stupid enough to design systems to store passwords in
plaintext anyway, this is an unreasonable expectation).  The strength of
the password against a brute-force attack if you have a 12 character
password that consists of only upper and lower case letters is _weak_,
and here is why:

 * 52 possibilities for each letter means that each character requires
   only 6 bits if you are storing a unique identifier for each
   character (with 12 such identifiers left as extras; two raised to the
   sixth power is 64).

 * The probability that there will be repetition in the password, given
   the low symbol count and the low available number of symbols to use
   is rather high.  Looking at the example that Gibson used above:

     - "g" appears 3 times
     - "c" appears twice
     - "z" appears twice
     - "n" appears once
     - "e" appears once
     - "m" appears twice
     - "a" appears once

   So, there are only 7 unique characters in that 12 character password.
   Armed with this knowledge, it is possible to generate a more targeted
   table for hash generation and greatly reduce the number of hashes
   required for a brute force attack (alright, not quite brute force,
   because we're talking about adding some intelligence to it, but it is
   still more or less brute force).

   In the above example, the number of possibilities for a password is
   95,428,956,661,682,176.  However, given the low entropy, a
   directed attack need only likely attempt as many as 8,031,810,176
   12 character hashes.  To give you an idea of how silly-low that is,
   I can compute 10 million hashes on 12-character values in about 14.5
   seconds on my system---using a single threaded program written in
   Python.  Add the ability to use all 6 of my CPUs, I could get that
   down to about 3 seconds.  Do it in a highly streamlined C or
   assembler program and I could probably do better than that by at
   least 10 times.

   This means that my system can compute 1 hash every 0.0000015 seconds.

   For the keyspace of 52 values, used in the "normal" situation, I can
   compute all likely combinations in about 70 hours on my system, using
   all of its CPUs and a Python program.  That is _not_ secure at all.

   Note that if a KDF is used and that KDF requires 0.01 seconds of CPU
   time, I go from an estimated 70 hours required to crack a single
   salted password to an estimated 700,000 hours (about 80 years) on my
   lone little computer.  Using 100 computers equipped like mine (not
   an unreasonable number of them!) it goes down to about 300 days, or
   just under a year.  Use an entire botnet to do it and you can STILL
   have the individual password in probably just minutes.

So, yeah.  Not secure at all.  Or, put better:  It's about as secure as
far too many systems on the Internet are, using replicated MySQL
databases to store plaintext passwords for your wonderful applications.

So the best advice is probably to use high-entropy passwords (like a
password card with symbols on it, which fits in your wallet and is far
better than Gibson's latin squares system), use a password for at most
ONE system (or at a stretch, family of systems in the same
administrative domain), use passwords that are at a bare minimum 12
characters (because on a secure system they aren't going to be cracked
anytime soon, especially if there is a strong KDF required to compute
the actual key), and do your best to steer clear of providers that don't
spend the time or money to make your security their business, as it
should be.

	--- Mike

-- 
A man who reasons deliberately, manages it better after studying Logic
than he could before, if he is sincere about it and has common sense.
                                   --- Carveth Read, “Logic”