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

[Ron Frazier]

Hi Mike,

Your posts always make me think about my positions.  I like that.  I'll 
stipulate right off the bat that you know more about cryptography than 
me, as is apparent by your reply.  However, I do have some further 
thoughts.  Steve Gibson's Password Haystacks page at 
https://www.grc.com/haystack.htm can be used to do the calculations to 
determine the brute force "attackability" of any password, strictly from 
a length and # of possible symbols point of view.  The page does not 
account for intelligent use of patterns, ie, they know your password is 
always an Uncle's first name followed by an Aunt's last name, etc.  At 
the bottom of your post, you mention using a high entropy password 
card.  When I see the term high entropy, I presume the password looks 
like gibberish, so, I'm going to assume that the passwords on such a 
card, as well as those from Steve Gibson's off the grid card will be 
equally non memorable to the user, even though the user may not like 
it.  One advantage of the grid over a password card is that the grid can 
be used to create passwords for any number of sites, whereas a password 
card can only hold a fixed number of passwords and still fit in your pocket.

By the way, if you just want a good string of high entropy gibberish, 
you can get that at https://www.grc.com/passwords.htm , up to 64 
characters.  These make good WPA passwords.  Another source of random 
data that Steve mentioned in the podcast is http://www.random.org .

For those that haven't looked at Steve's site, I'll just share a bit of 
background.  His objective is to start with the domain name of a 
website, and using only a piece of paper with a special grid on it, to 
create a password for the site.  As a baseline, he uses a 26 x 26 Latin 
Square.  This is a chart with 26 rows and 26 columns.  Each row contains 
the full alphabet and each column contains the full alphabet with no 
duplications in either row or column.  You can print your own custom and 
unique Latin Square from his website or use your own algorithm.  Using a 
procedure he gives, which you also could change, you traverse into the 
grid to a certain starting point using part of the domain name of 
interest.  Then, you traverse through the grid either up and down or 
left and right, also using the domain name to trigger your movements.  
At each point, you encipher the character you're working on by choosing 
2 other characters from the grid.  Thus, amazon, in his example, gets 
enciphered into a 12 character password that can be used for that website.

Now, continue below.  See further comments inline:


On 9/3/2011 2:29 PM, Michael Trausch wrote:
> 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.
>
>    
I don't think Steve is advocating using a 12 character password with 
only upper and lower case letters if you have a choice.  He is simply 
acknowledging that many websites will not accept anything else.  I am 
sorry to say that both my bank (which shall remain nameless) as well as 
the job posting website of a major national defense lab (which shall 
also remain nameless) both limit me to 8 characters.  I find this 
abominable, but it is what it is.  There are many many examples of 
websites that won't allow numbers or symbols, while others will require 
it.  I will explain later how Steve's grid can be used to a) add length 
to the password, b) add symbols, or c) add numbers; all of which 
increase the entropy and security.  The method Steve describes will 
allow a reasonably secure high entropy password (within the constraints 
of the length) to be created for any website based on the domain name, 
or recreated if necessary, assuming you don't lose the grid.  He's 
trying to make it so it can be put into any site without it complaining 
about length, symbols, or numbers.  He's also trying to make the 
procedure easy to remember so you don't have to remember 20 different 
methods to traverse the grid for 20 different websites.  Adding length, 
symbols, or numbers will certainly help your security, but will make 
more an more sites reject the password.
> 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.
>
>    
The password haystacks page agrees with your math with one exception 
which I'll describe below.  If I put the password used in Steve's 
example, gcznegmacmzg, into the password haystacks page, it says the 
following:

Count of all possible passwords with this alphabet: 99,246,114,928,149,462
Time to crack it - Online attack - 1000 guesses / second: 31.56 thousand 
centuries

Note that this is the exact scenario that the grid was designed to 
defend against.  Note also that, if you're trying to crack my Amazon 
account with a password like this, it is highly likely that the system 
will lock you out after 3 or 10 guesses for anywhere from 30 minutes to 
a day.  This will substantially lengthen the time frame you'll need to 
crack it.

The number of possible passwords is very close to your number.  I'm not 
sure why the small variance.  However, this is using only 12 LOWER case 
characters as the symbol set, with 26 possible characters.  If I just 
change the last character to a (capital) G, which brings upper case into 
the picture, so we have 52 symbols, the new data is thus:

Count of all possible passwords with this alphabet: 
398,541,261,515,392,353,540
Time to crack it - Online attack - 1000 guesses / second: 1.27 hundred 
million centuries

So, I think my Amazon account would be secure enough, based on the 
online attack threat model, using a password of this type.  I should 
point out that, since this password starts with a G, and not a Z, and if 
you're trying passwords in alphabetical order, you might hit it in only 
.4 hundred million centuries.  I think I can live with that risk.  8-)

>     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.
>
>    
OK, now you're talking about an offline attack, and things change a 
bit.  I presume you're referring to a Key Derivation Function (thanks 
Wikipedia) to slow down the user's password tries just enough to 
discourage brute force attack.  So let's see what password haystacks 
says.  This page gives two more numbers as follows (using a 52 character 
symbol set of length 12):

Time to crack it - Offline fast attack - 100 BILLION guesses / sec: 1.27 
centuries.  Still pretty secure, I think.  (I'm assuming this is 1 machine.)
Time to crack it - Massive cracking array - 100 TRILLION guesses / sec: 
1.52 months.  (I'm assuming this is 1000 machines.)  (Note, if I go back 
to the lower case "g" as the last character, this drops to 16.54 
minutes, so I could understand how you'd be skeptical.)

OK, now we have a potential problem with that last item.

IF every query from every machine is subjected to a KDF, as you 
mentioned, and if only 100 queries / sec. can be done, there is no 
problem.  We're working at 1/10 the speed of the original example (with 
52 characters), so it will take 12.7 hundred million centuries to 
crack.  No problem.

If every machine is subjected to a KDF but you can submit 1000 
simultaneous queries from different machines, that's a bit different.  
I'm not sure how to do that math, but I THINK, you're still talking 
about a hundred million centuries.  Still no problem.

The big problem is if there is no KDF and all 1000 machines can submit 
queries at the maximum speed.  This is how we might crack the password 
in 1.52 months.  So, I will admit that if you have 1000 computers at 
your disposal AND you want to crack my Amazon account with a 12 
character Upper / Lower case password AND their system doesn't foil you 
with KDF's or lockouts, then I could be in danger.  So, I should 
probably increase the length of the password or add symbols or numbers.  
I'll post something later (after supper) to show how to do that with 
Steve's grid.  For, now, if I just add one number and one symbol to the 
password on the password haystacks page, which increases the potential 
symbol set to 95 symbols and length to 14, even a massive cracking array 
will take 15.67 thousand centuries to crack my password.  I think that's 
secure enough now.  More later.

Sincerely,

Ron

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

-- 

(PS - If you email me and don't get a quick response, you might want to
call on the phone.  I get about 300 emails per day from alternate energy
mailing lists and such.  I don't always see new messages very quickly.)

Ron Frazier

770-205-9422 (O)   Leave a message.
linuxdude AT c3energy.com