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

[Michael H. Warfield]

All,

I'm sorry, but I'm going to top post on this one...  This will be a bit
of a rant (and long) but mild for me and I'll keep the math level
reasonable...

Oh, here we go again...

http://www.xkcd.org/936/ 
http://isc.sans.edu/diary.html?storyid=11350 
http://www.xkcd.com/538/ 

Lets see...  The dudes that do xkcd seriously DO seem to know something
about cryptography and entropy.  I'm impressed!  There's a very subtle
clue to that in the first reference.  The first URL is "Through 20 years
of effort, we've successfully trained everyone to use passwords that are
hard to remember, but easy for computers to guess."  So true.

Important thing to note about that xkcd cartoon (the first clue)...
They attribute 11 bits of entropy to each word.  Believe it or not, that
tells me that they really do know something about what they're talking
about.  That is exactly the entropy derived from the random selection of
words from a 2048 word lexicon.  There may be one or two on this list
who might be familiar with Bellcore's old "S/Key" OTP (one time
password) system.  Something similar to the RSA tokens only algorithmic
based (based on a one-way hashing function) rather than time based.
This was codified in RFC 2289, <http://www.ietf.org/rfc/rfc2289.txt> "A
One-Time Password System", the IETF OPIE / S/KEY RFC (the lexicon is in
Appendix D).  OPIE stands for "Onetime Passwords in Everything".  You
can get free OPIE calculators for Palm, Android, and (I think) iPhone.
You could enter the response to the challenge as a 64bit hex string or a
string of 6 words seperated by spaces that was the equivalent.  For the
later, they have a lexicon of 2048 words from 1 to 4 characters long (so
none of the xkcd words would be in it since they were all too long).
2048 = 2^11 so you get 11 bits of entropy per RANDOM word from the
lexicon.  True OPIE uses 6 words for 66 bits of entropy.  It's actually
64 bits of entropy since that standard uses 2 of the bits for a parity /
checksum, but the lexicon is usable and works for much MUCH more.

You can use the lexicon for generating your own passphrases and they can
be as long as you like.  You can also use a different lexicon as long as
it has 2048 words in the list.  It uses no numerals or punctuation and
only mono-case (default is all upper case - flavor to taste).  If you
like, you can always jigger the case or add a number or some punctuation
if you care, but OPIE only uses upper case for validating login's using
the OTP algorithm.  (You can actually enter an OPIE authentication
string in any case or mixed case - it maps them.)  Since they are all
English words, they are all pronouncable and understandable.  Still got
problems with "red" and "read", "for" and "four", "one" and "won", and
"too", "to", and "two" but that's just our delightful English language
at work there.  You can deal with it.

I recently had to deal with this situation designing a system where one
designer suggested using this for a password generator (we only needed
random password generation but a human may have to type it on some
hopefully rare day...).

< /dev/urandom tr -dc A-Za-z0-9_ | head -c8

Y0anE48h
rawxT_FL
Jh2fMiTu

Gee...  Anyone think that's any good?  Show of hands?

Here's the math.  There's 63 characters in his character set.  Lets be
generous to my cohort and add one to expand that to 64.  Makes it a nice
64 characters and makes the math easy.  64 == 2^6 or 6 bits of entropy
per character given a true random generation.  8 characters -> 48 bits
of entropy.  Still think that's so good?  Try reading it to a user over
the phone and have him type it in (recovery password when he can't even
boot his encrypted laptop).  Think he'll get it right the first time (or
ever)?

Ok...  Let's match a 6 word OPIE string which has 66 bits of entropy.
Oh!  The math is really easy (yeah, I cheated, I made my example super
easy to match - but I'm really just setting simplified limits on the
problem set and will apply perturbations to it below)!  11 characters at
6 bits per character has the exact same entropy as 6 plain English words
chosen from a lexicon of 2048 short words at random (11 bits of entropy)
with nothing special!  Wow...

Now, I have a ranpass.sh password generator based on OPIE that will
generate a passphrase from 6 to 20 words from the OPIE lexicon...  Let's
look at a few outputs.

"ITS BAT JILT WEAL MEN SUD"
"ANT KURD DUNK LIP TIME GUS"
"DOG TAN IDEA KURT BELL BUN"
"SNAG GETS EAT DADE ADDS TWIN"

Ok...  Those all have 66 bits of entropy.  You want more, go to 8 words:

"HEM IF CUP ANEW SHAW GAGE NUDE SILO"
"CLOG ROME OWLY ED GRIM TINY NAGY GAG"

That's 88 bits of entropy and it really is!

Do they look like strong passwords to you.  Many people who say no.  I
would bet a lot of experienced admins would have a knee jerk reaction
and say they weren't.  Think again.  Yeah, they really are.  Stronger
than what you're likely to dream up.

Now...  Can you remember those?  Actually I can but I'm a little
different from most people.  I have done 16 or more in a single short
reading.  I do handle 8 without breaking a sweat.  It's mnemonic a
trick.

Could I remember those three from my collaborator?  Hell no.  And those
are only 8 characters!  Ok...  So you're no worse off, memory wise, with
those long passphrases than the jerky 11 character string.  [Which just
coincidentally happens to be the length of the "Tr0ub4dor&3" string in
xkcd.  Hmmm...  Cute guys.  Dropping hints?  Clue number 2?)

Ok...  How about a little test.  Cracklib.

[mhw at canyon ~]$ cracklib-check < cracklib.test 
ITS BAT JILT WEAL MEN SUD: OK
ANT KURD DUNK LIP TIME GUS: OK
DOG TAN IDEA KURT BELL BUN: OK
SNAG GETS EAT DADE ADDS TWIN: OK
HEM IF CUP ANEW SHAW GAGE NUDE SILO: OK
CLOG ROME OWLY ED GRIM TINY NAGY GAG: OK

The cracklib-check utility passes password candidates through the
"FascistCheck" routine in cracklib.  I don't even care why it might
fail.  If it fails, it's no good.  If it passes, you're probably in
pretty good shape from ANY password cracker.

Oooo...  Cracklib FascistCheck likes them.  That will pass a "strength
based" password checker like pam-cracklib and John the Ripper will never
even come close to busting them.  Even the password strength checker in
my Revelation password safe likes them and says they're good and very
strong, even though its generator would never generate them.  But it
won't get you past the complexity checkers that demand that you must
have at least 3 of the 4 categories of upper case, lower case, numerals,
and punctuation.  XKCD got it right!  Dead on.

[And I still DO NOT BELIEVE the MORONS who write web pages that limit
your passwords to no MORE than 8 characters - yeah, I still see them.]

Those passwords are stronger than anything most carbon based lifeforms
will come up with and yet they are easy to type in and easy (for some)
to remember it just take a few more hits on the keyboard (but you really
ARE going to use copy-n-paste from a keyboard safe, now aren't you?  Be
honest now.).

Now, those are purely random generated.  A real user won't do as good.
Telling a user "8 or more characters with upper and lower case and a
number or symbol" really doesn't cut it.  Even "11 or more characters
with upper, lower, numerals, and symbols at total random" won't get you
even close, due to human nature.

Now...  Back to the earlier math.  I made that math simple by setting
the character set to 64 characters.  What if we can make it better?  If
we expand it with common symbols we can get out close to 72 or maybe 80
if we really stretch it.  That really only expands your entropy to maybe
around 6-1/2 bits per character, if it's truly random.  In fact, if you
take every 7 bit possibility, including control characters, NULL, and
ESC, you only get to 7 bits of entropy (128 characters in the set).
There's your boundary conditions.  You've only added one bit of entropy
per character and do you seriously think THAT's practical?  So, best you
can really hope for from a random password generator that generates a
truly password from a character set from 64 to 94 characters (drop the
controls and a couple more - seriously) is less than 7 bits of entropy
per character.  From carbon based life forms, you're lucky if you get 3
bits.  None of us really know what random is or how to generate it.

If anyone cares, I've attached my ranpass.sh generator, which includes
the OPIE lexicon of 2048 words.  Generate a few and play with caps and
color by prefixing it with a digit like "1 " and ending with a
punctuation like "[.!?,.]" to get it pass the complexity checkers...

Bottom line is that none of this really helps in the real world of
password sniffers, keyloggers, and the anatomy of a hack anyways.  And
periodic forced password changes make it even worse by adding more
opportunities for password sniffers and trojans to go to work.  Sigh...
We got it wrong.

Here...  Final word...  You don't want totally random but you want
something strong that will zip past the stupid complexity checkers?
Seriously try something like this...

monk2frog: Read that back again!
dress4girl: It's only purple, too bad...
leaf0tree: It's fall now - bye bye.

Ok...  You've got two patterns in there.  Two objects separated by a
number, "monk2frog:", "cart2horse:", "doll4girl:" etc, etc, etc, and
ending with some punctuation.  LOTS of possibilities.  You got your
number and your punctuation right there.  You got 3 of the 4 categories
in one sweep.  Now add a simple nonsensical statement (yeah, I love
Louis Carol for things like this...) and you got caps and another
punctuation along with some spaces.  They will never bust it.  Still
doesn't even come close to what the full random OPIE space will do but
pretty damn good.

A monk yells at a frog working on a book yelling "Read that back again!"

You'll remember it months...

I do eat my own dog food.  I really do use systems like these.  They
work.  They work well.  Just pisses me off when I have to change one for
no bloody good reason.


Regards,
Mike

On Sat, 2011-09-03 at 15:38 -0400, planas wrote: 
> Hi folks,

> On Sat, 2011-09-03 at 14:29 -0400, 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.
> > 
> > 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
> > 
> 
> As Mike pointed out, any password can be broken with enough computing
> power and sufficient time. The real issue is that most people tend to
> use the same password or the a very small number of passwords. The real
> problem is once a cracker gets the password and email account the user's
> identity can be compromised easily. Often users have easily cracked
> passwords. I know of people who will use word combinations like
> redsturgeon because it is "too hard" to use random characters. They are
> always asking are people able to crack their email, etc.
> 
> -- 
> Jay Lozier
> jslozier at gmail.com
> 
> _______________________________________________
> Ale mailing list
> Ale at ale.org
> http://mail.ale.org/mailman/listinfo/ale
> See JOBS, ANNOUNCE and SCHOOLS lists at
> http://mail.ale.org/mailman/listinfo

-- 
Michael H. Warfield (AI4NB) | (770) 985-6132 |  mhw at WittsEnd.com
   /\/\|=mhw=|\/\/          | (678) 463-0932 |  http://www.wittsend.com/mhw/
   NIC whois: MHW9          | An optimist believes we live in the best of all
 PGP Key: 0x674627FF        | possible worlds.  A pessimist is sure of it!
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ranpass.sh
Type: application/x-shellscript
Size: 15053 bytes
Desc: not available
Url : http://mail.ale.org/pipermail/ale/attachments/20110903/946ff92a/attachment-0002.bin 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 482 bytes
Desc: This is a digitally signed message part
Url : http://mail.ale.org/pipermail/ale/attachments/20110903/946ff92a/attachment-0003.bin