Technology Blog

Due to time constraints, I am going to have to split this week’s
crypitcide posting into two parts - I have a lot going on at work, and
this weekend likewise, so I will cut down to the meat of the matter
and then dress it up with some finesse in the next few days.

As I implied in Crypticide I, my attempt to kill the Unix crypt()
algorithm has been going on for over 13 years now. A few more weeks
won’t make much difference.

So, consider the figure of “6.7 trillion” as computed here:

1+95^1+95^2+95^3+95^4+95^5+95^6+95^7+95^8 =

6,704,780,954,517,121 decimal =

17,d1f6,7717,3e81 hex =

10111,11010001,11110110,01110111,00010111,00111110,10000001 binary

…the number occupies 7 bytes; it fits comfortably within a 64 bit
word, leaving at least 8, if not 10 or 11 bits spare, to play with for
other encoding purposes.

Alas that is the number of plaintext passwords that we computed last
week, on the assumption of using the 95-character typeable keyboard
characters in standard ASCII. As previously stated I recognise that
this is no longer a cast-iron certainty that people’s passwords are
entirely composed of 7-bit ASCII, but it’s a pretty good assumption
for a significant portion of the world’s computing userbase.

In short: it’s a good enough assumption that it can bite, painfully.

Now: let’s think around some of the implications of this math.

First, think of this in terms of storage requirements. In calculating
how many passwords exist (6.7 trillion) we have also (excluding
metadata) computed approximately how much storage is needed to create
a dictionary that contains every possible password:

95^0 = 1 (one, zero-length password; 1 byte, or specialcase it)

95^1 = 95 (95, 1-char passwords, 95 bytes)

95^2 = 9025 (9025, 2-char passwords, (9025*2) bytes = 18050 bytes)

…

So, following that math:

((95^1)*1)+((95^2)*2)+((95^3)*3)+((95^4)*4)+((95^5)*5)+((95^6)*6)+((95^7)*7)+((95^8)*8)

53,566,920,179,174,020

which is this much storage:

53566920179174020 / (1024^4)

48,718

About 49,000 Terabytes. That sounds like an awful lot, doesn’t it?
Enough to be secure even in this day and age?

The thing is, you don’t need to do that. More later.

For those of you who want to experiment with the maths, I
recommend use of the Unix arbitrary precision calculator /usr/bin/bc
as available on most Unix flavours; I am writing this article on an
Apple iBook and am using bc with its ibase and obase
converters to produce most of the maths for this series of articles,
and pasting the computation directly into the window, merely adding
commas for clarity. Hopefully this should reduce risk of typos, etc,
going unspotted.

Crypticide Project RSS:
[www.crypticide.com]

[Comment Link for RSS]

source: Crypticide III(a): Number of passwords

Simply put: the problem with reusable passwords as a form of
authentication is that there are too few of them.

This goes for all sorts of passwords in the modern day, not just Unix
passwords; I find the latter particularly egregios for reasons that I
will explain another time, but for the moment let’s speak about
simple, short passwords.

The maths are easy: for example, if you have a 4-digit PIN code
protecting an ATM card, there are 10,000 combinations, from 0000
through 9999; because there are ten digits and four fields to fill,
the maths work out:

10 ^ 4 = 10,000 (”ten to the power of four”)

Following this, we can determine precisely the number of passwords
that exist for any given authentication system.

The traditional Unix password algorithm accepts up to eight characters
of 7-bit ASCII keyboard input; those characters which exceed 7 bits
are stripped to fit. From the fact that passwords of eight characters
or less, we have the following math, where there are n possible
characters available to the typist:

1 + (the empty password)

n^1 + (all 1 character passwords)

n^2 + (all 2 character passwords)

n^3 + (…yadda…)

n^4 + (…yadda…)

n^5 + (…)

n^6 + (…)

n^7 + (…)

n^8 (…up to and including all 8 character passwords)

So: all we need do now is determine a value for n; this is
debatable, but the basic count is easy:

26 uppercase letters: A-Z

26 lowercase letters: a-z

10 digits: 0-9

32 ASCII punctuation: !”#$%&’()*+,-./:;<=>?@[\]^_`{|}~

1 SPACE

Making a basic total of 95 typeable characters; a long time ago I had a
long discussion on USENET with the likes of Steve Bellovin and some
others (alas apparently not archived on Google) regarding whether it
was wise to include the likes of TAB and other control characters in
the possible “typeable” password set.

The discussion was varied - and to be honest, politely inconclusive;
TAB can be used to swap between input fields in GUI environments,
Ctrl-A moves to the start-of-line in some likewise, Ctrl-H may or may
not be interpreted as Backspace in raw line disciplines.

In short it’s a mess, so let’s stick to n = 95 and ignore
internationalisation issues for the moment.

Therefore:

1+95^1+95^2+95^3+95^4+95^5+95^6+95^7+95^8 = 6,704,780,954,517,121

There are about 6.7 quadrillion “typeable” Unix passwords.

That’s not very many.

Really. Honestly. I mean it.

I’ll explain why, next thursday.

[Comment Link for RSS]

source: Crypticide II: Passwords: there are too few of them.

Thirteen years ago, on 15th June 1991, I posted v2.7a of Crack to
the newsgroup alt.sources
[groups.google.com]
- I messed-up the posting process a bit, since these were the days
when people cared about netiquette, the Web was multicast and named
USENET, and also this was perhaps the first time I was
releasing software to a wide and critical audience.

It became a very popular piece of software indeed.

Crack began as a homebrew refinement of the “pwc” password-checking
software that people could find included in Dan Farmer’s COPS
package
[groups.google.com]
- but my copy of which was the COPS cracker’s ancestor, some much
older code that was circulating amongst the UK’s Unix/CompSci
community in the mid/late 1980s.

The concept of a program like Crack goes back many many years (see
[groups.google.com]
[groups.google.com]
[groups.google.com]
for some discussion, and see also earlier papers by Morris and
Thompson) and the basic method of password cracking is easily
described to any layman who can follow a recipe:

1. for each word in a dictionary listing of words
   
2. … see whether anyone is using that word (eg: “sesame”) as a password
   
3. … see whether anyone is using obvious variants of that word as a password
   (eg: “sesame1″, “2sesame”, “ses3ame”, “sesame69″, “s3sam3″, “SESAME”, …)
   
4. … and move on to the next word, and repeat.
   

In fact the concept is so utterly simple that it can be expressed in
less than a single line of the Perl programming language:

World’s smallest password cracker?

echo SESAME | perl -nle ’setpwent;crypt($_,$c)eq$c&&print”$u=$_”while($u,$c)=getpwent’

…but before delving into technological issues any further, a little
history is appropriate.

In the autumn of 1990 I began messing-about with the “pwc” source; as
a programmer I found the original memory-management /
wordlist-handling code rather ugly (not to mention: barely
comprehensible) but in rewriting that I found the resultant tool to
be suddenly much more effective at guessing passwords.

I suspect that I inadvertently fixed some string-handling bug in the
original code; in any case, I now had a tool that was efficient,
useful, and interesting to play with, in my role as systems programmer
at a Welsh university.

Versions 2.0 and upwards of Crack were total rewrites for clarity and
extensibility, plus wrapper scripts and other oddments to perform
housekeeping.

Version 2.7a was the first public release to USENET,
and barely a few weeks later, after discussion and issuing public notice
[groups.google.com]
[groups.google.com]
I posted v3.2a of Crack
[groups.google.com]
which contained a faster version of the Unix password hashing
algorithm, one spawned from Bob Baldwin’s code which I’d further
tuned/rewritten to get an extra 40..50% performance boost.

That was the day everything changed for me.

On mundane machines like Sun’s 3/60 Workstation, you could now check
thirty-five passwords per second, as opposed to the three per second
permitted by the slow “libc” implementation of crypt(). After
a little math:

35 * 60 * 60 * 24 * 2 = 6,048,000

…that’s about 6 million password-checks that you could make, per
weekend, per CPU. Multiply that by the twenty or so workstations in
the student laboratory, and you could do some serious checking of
password security:

6048000 * 20 == 120,960,000

Almost one hundred and twenty-one million password guesses in a
weekend. That - in 1991 - was an astounding amount. If you had
(say) 50 users in your password file, that was 2.4 million guesses
apiece, each guess to see if someone had used dictionary word, or a
StarTrek character name, or the name of a chemical compound, or a
girl- (and boy-) friends’ name (etc) as their password.

That was a lot of guesses.

As an aside: on a modern PC the same can be achieved on a single
CPU, taking between 5 and 20 minutes to complete.

There was some dissent about the software, however there was much
much more support,
[groups.google.com]
both of which seemed odd given that both the technique and technology
were so old. To my mind the truth is that up until the next version
(4.0a)
[groups.google.com]
there was actually very little in Crack that had not been in one or
other previous password-cracking program.

The 4.x series of Crack (3 Nov 1991 onwards) introduced first the
programmable dictionary generator so that people could “get creative”
with their guessing; it also introduced networking, so that you could
automatically distribute the embarrassingly-parallel load of
your password cracking amongst dozens, perhaps scores of machines.

In this era, this was really cool; remember that this predated any of
distributed.net, the RC5 project,
SETI@Home, Genome@Home, Folding@Home,
peer-to-peer or the like; to be able to draw-together the resources of
an entire university to address a single, linearly-scalable compute
problem was quite enlightening for some computer scientists.

Bizzarely (to modern ears) I was essentially forbidden from referring
to this innovation as “parallel computation” - a term which meant
something quite different to
purist British ears in that era; terms like distributed or grid
computing were unknown to me at the time, or possibly did not exist
outside of CompSci hothouses - or even at all?

Interest in Crack and password-cracking mushroomed; people wrote
Bachelors’, Masters’ and even one Doctorate thesis about it.
Sysadmins were lauded for running it. Students were reprimanded or
expelled for running it. Imitations sprang up. People of every
motive posted better, faster, geekier, more tuned versions of the
crypt() routine for particular architectures. Some messed around with
their benchmarks to suit their egos
[groups.google.com]
- and some have subsequently gone on to build excellent professional
reputations on the back of such work.

Not all of them have yet bought me beer, but some have done. That,
plus reputation and all that that brings, is the profit that I have
reaped from this early exercise in Open Source Software distribution.

Eventually matters calmed down; a few years later the WWW/Web was
invented, Perl5 was released, Dan Farmer and Wietse Venema released
SATAN and all the Crack-style hyperbole and
flamage was once-again repeated, as indeed Crack’s release expanded
upon that which greeted the release of
COPS.

Now that there are scores of
potentially dual-use (ie: cracker/admin) tools available to the
general public, the flamage seems to have died down except where truly
media-friendly scary hax0r-nerds are involved.

So: thirteen years ago. Thirteen years ago, today. Aside from
nostalgia, why bring all this up, now?

Because I want that password algorithm - the traditional,
8-character Unix password-hashing algorithm - dead.

Watch this space for updates.

[Project RSS] [www.crypticide.com]

[Comment Link for RSS]

source: Crypticide I: Thirteen Years of Crack