Re: Private Key Generation from Passwords/phrases

2007-02-04 Thread Allen



Alexander Klimov wrote:

[snip]


(Of course, with 60K passwords there is almost for sure at
least one password1 or Steven123 and thus the salts are
irrelevant.)



I'm not sure I understand this statement as I just calculated the 
 HMAC MD5 for password1 using a salt of 7D00 (32,000 decimal) 
and got the result of 187de1db3348592a3595905a66cae418. Then I 
calculated the MD5 with a salt of 61A8 (25,000 decimal) and got a 
result of 9cad6ac9fd6c09fd8e99e478381f.


Are you saying that the salt is irrelevant because a dictionary 
attack is fast and common dictionary words would allow an easy 
attack?


Thanks,

Allen


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Private Key Generation from Passwords/phrases

2007-02-03 Thread Alexander Klimov
On Sun, 28 Jan 2007, Steven M. Bellovin wrote:
 Beyond that, 60K doesn't make that much of a difference even with a
 traditional /etc/passwd file -- it's only an average factor of 15
 reduction in the attacker's workload.  While that's not trivial, it's
 also less than, say,  a one-character increase in average password
 length.  That said, the NetBSD HMAC-SHA1 password hash, where I had
 some input into the design, uses a 32-bit salt, because it's free.

In many cases the real goal is not to find all (or many) passwords,
but to find at least one, so one may concentrate on the most-oftenly
used salt. (Of course, with 60K passwords there is almost for sure at
least one password1 or Steven123 and thus the salts are
irrelevant.)

-- 
Regards,
ASK

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


RE: Private Key Generation from Passwords/phrases

2007-02-03 Thread Anton Stiglic
Bill Stewart wrote:
Salt is designed to address a couple of threats
- Pre-computing password dictionaries for attacking wimpy passwords
...

Yes indeed.  The rainbow-tables style attacks are important to protect
against, and a salt does the trick.  This is why you can find rainbow tables
for LanMan and NTLMv1 hashed passwords, but not for NTLMv2.
This to me is the most important property achieved with a salt, and the salt
doesn't have to be that big to be effective.

--Anton




-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Private Key Generation from Passwords/phrases

2007-01-30 Thread Steven M. Bellovin
On Mon, 22 Jan 2007 16:57:34 -0800
Abe Singer [EMAIL PROTECTED] wrote:

 On Sun, Jan 21, 2007 at 12:13:09AM -0500, Steven M. Bellovin wrote:
  
  One sometimes sees claims that increasing the salt size is
  important. That's very far from clear to me.  A collision in the
  salt between two entries in the password file lets you try each
  guess against two users' entries.  Since calculating the guess is
  the hard part, that's a savings for the attacker.  With 4K possible
  salts, you'd need a very large password file to have more than a
  very few collisions, though.  It's only a benefit if the password
  file (or collection of password files) is very large.
 
 Definition of very large can vary. (alliteraiton intended).  Our
 userbase is about 6,000 active users, and over the past 20 years
 we've allocated at least 12,000 accounts.  So we definitely have
 collisions in 4k salt space. I'm not speaking to collisions in
 passwords, just salts.
 
 UCSD has maybe 60,000 active users.  I think very large is very
 common in the University environment.
 
Is that all in one /etc/passwd file (or the NIS equivalent)?  Or is it a
Kerberos KDC?  I note that a salt buys the defense much less in a
Kerberos environment, where capture of the KDC database lets an
attacker roam freely, and the salt simply protects other sites where
users may have used the same password.

Beyond that, 60K doesn't make that much of a difference even with a
traditional /etc/passwd file -- it's only an average factor of 15
reduction in the attacker's workload.  While that's not trivial, it's
also less than, say,  a one-character increase in average password
length.  That said, the NetBSD HMAC-SHA1 password hash, where I had
some input into the design, uses a 32-bit salt, because it's free.



--Steve Bellovin, http://www.cs.columbia.edu/~smb

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Private Key Generation from Passwords/phrases

2007-01-30 Thread Abe Singer
On Sun, Jan 28, 2007 at 11:52:16AM -0500, Steven M. Bellovin wrote:
  
 Is that all in one /etc/passwd file (or the NIS equivalent)?  Or is it a
 Kerberos KDC?  I note that a salt buys the defense much less in a

For SDSC, one file.  For UCSD, not sure, but I suspect it's (now) a KDC.
(Brian, are you on this list?)

 Kerberos environment, where capture of the KDC database lets an
 attacker roam freely, and the salt simply protects other sites where
 users may have used the same password.

Agreed.

 Beyond that, 60K doesn't make that much of a difference even with a
 traditional /etc/passwd file -- it's only an average factor of 15
 reduction in the attacker's workload.  While that's not trivial, it's
 also less than, say,  a one-character increase in average password
 length.  That said, the NetBSD HMAC-SHA1 password hash, where I had
 some input into the design, uses a 32-bit salt, because it's free.


I don't disagree with you.  I was just addressing your implication
(or at least, what I *read* as an implication ;-) that  4096 users
was rare.

FWIW, the glibc MD5 crypt function uses a 48-bit hash.

also FWIW, salt lengths significatly affect  the work factor and storage
requirements for pre-computated hashes from dictionaries.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Private Key Generation from Passwords/phrases

2007-01-24 Thread Bill Stewart



 With 4K possible salts, you'd need a
 very large password file to have more than a very few collisions,



Definition of very large can vary. (alliteration intended).[...]
UCSD has maybe 60,000 active users.  I think very large is very common
in the University environment.


Different decade, different threat models, different scales.
It was probably pretty rare to have more than a
couple of hundred users on a PDP-11,
but even at 60-70 you're in birthday-collision range with a 12-bit salt.
But a website could easily have a million users in its password files,
and some systems like Yahoo and Hotmail have hundreds of millions,
though obviously they're not all separate Unix userids.
Sometimes it matters if they get stolen, sometimes not -
I don't care if someone discovers that
my New York Times web password is password,
but I'd be really annoyed if my online banking password got cracked.

Salt is designed to address a couple of threats
- Pre-computing password dictionaries for attacking wimpy passwords
These become harder to do online, pushing a dictionary of
e.g. a million words to 4 billion, or ~32GB,
an unreasonably large database for ~1975 crackers,
though obviously you could use a manageable stack of tapes.
Today that fits in my iPod, though it's still impractical
to store an unsalted full-56-bit DES password dictionary.
- Detecting password collisions within systems, and between systems
Testing a known password against 4096 salts
took a long time at 0.5 MIPS, but it's faster at 4000 MHz.
Large systems will have internal collisions,
and the web makes it even more likely that somebody
will have logins on insecure systems
that might have the same password as their secure logins.
- Annoying then-hypothetical hardware DES crackers
That's still useful against some designs today,
though many designs, especially software,
are table-driven in ways that aren't annoyed much.

There are probably times that salt is useful, and that password files
using hashes are useful, but I'd think that if you're going to do that
today you might as well use 64 or preferably 128 bits of salt,
and of course you might want a hash other than MD5 or SHA-1.


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Attacking the hash (WAS: Private Key Generation from Passwords/phrases)

2007-01-24 Thread Allen

Hi gang,

As an outsider, sort of, looking in I had an interesting thought 
about this. Since insider threats are the biggest problem, what 
vector could an insider use against password hashes to gain root 
password access?


The problem with Rainbow tables is that they would be too massive 
when the salt was 4096 to be practical unless you had the power 
of NSA or an equivalent supporting your efforts.


However, what about attacking the salt? How good is the PRNG for 
the salt? Is it at all predictable?


Here is one approach that might work. Keep entering the same 
password(s) and collecting the resultant hashes until you get 
several duplicates. Then analyze the results to see if there is a 
pattern to the repetition that would allow for a birthday attack 
against the salt that would allow an attack against the root 
password hash or other administrative rights password hashes that 
could be collected.


I suspect this would be somewhat difficult to code but once done 
almost the entire attack could be done off-line on a machine that 
uses the same password hash creation mechanism so you wouldn't 
trigger an IDS or similar audit process on the network under attack.


Given the long history of industrial espionage in the corporate 
world I'm sure that there are probably small teams working to 
collect information that have somewhat more resources than an 
individual or outsider group might have, making the effort 
required feasible.


Thoughts?

Best,

Allen

Leichter, Jerry wrote:

| ...One sometimes sees claims that increasing the salt size is important.
| That's very far from clear to me.  A collision in the salt between
| two entries in the password file lets you try each guess against two
| users' entries.  Since calculating the guess is the hard part,
| that's a savings for the attacker.  With 4K possible salts, you'd need a


[snipped]

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Private Key Generation from Passwords/phrases

2007-01-23 Thread Matthias Bruestle
Joseph Ashwood wrote:
 I'm going to try to make this one a bit less aggregious in tone. I'm also

Thank you.

 - Original Message - From: Matthias Bruestle
 Joseph Ashwood wrote:
 - Original Message - From: Matthias Bruestle

 You also ended up removing a large portion of my point. My primary point
 was
 that 2^76  2^112. You made several assumptions in coming to your
 conclusion that are at least suspect.
 
 You observe that currently 3DES:ECC-224 speed is about 4000:1, and assume
 that it will stay this way. However, if you look at the history of ECC, the
 speed of ECC doesn't scale linearly against 3DES, in fact a single
 thread of
 3DES might've actually been faster 1 year ago (during the GHz war, before
 multi-core), whereas ECC is still improving as the ability of the CPU to
 perform complex routing and branch prediction improves. So next year the
 ratio could be 100:1, I doubt it will be that dramatic but it is possible.
 As a result this assumption will have to be reexamined every time a CPU
 revision is released, a slight timing change can actually make a big
 difference to the 3DES:ECC speed ratio. Also you need to consider the
 attack
 speed of the attacker, versus the production speed of the user.

I know there are likely some shifts. Hence I wrote The relation stays
(mostly) the same. But in my opinion these shifts are minimal compared
to all the other uncertainties, e.g.:

- How long does the protected secret/signature be ok?
- How well is your adversary funded?
- How much entropy has the passphrase really?
- How much is the general speed increase in the next 20 years?
- ...

If you calculate your bits without safety margin, then next year AMD
could add a 3DES unit to an CPU, the speed ratio is 4:1 and you're
busted. (Because of the hardware friendly design of DES I would say a
faster 3DES is easier to get than a faster ECC.)

 You assume that the fastest way to computer point exponents is through
 counting up to the exponent. While I admit I'm not familiar with point
 exponentiation algorithms, I strongly suspect this one to be incorrect, I
 see no immediate reason that (k*k*k*k) must be decomposed to (((k*k)*k)*k)
 instead of ((k*k)*(k*k)), at exp=4 there is no difference but at
 exp=16million there is an enormous difference. You might be able to make
 this assumption true for your system by somehow proving that the only
 way to compute k^x requires b^x steps (for some b.

My assumption is that the passphrase is properly processed, i.e. nicely
hashed. So an attacker has to go through this process if he wants to
exploit the reduced entropy of the passphrase and (at least) I see no
way how to exploit this reduced entropy then to help algorithms like
Pollard's rho/lambda to speed up the computation. The attacker may use
any point multiplication method he wants to use. (Jacobian, modified
Jacobian, NAF, windowing, ...)

 I see no reason it the arguments presented that the attacker would still
 have to perform 2^76 (ECC)work in 2^112 (3DES)time, instead of 2^76
 (ECC)work in substantially less than 2^112 (3DES)time.

An attacker would have to perform 2^100 (ECC)work, because the ratio
accounts in my calculation only for 2^12 steps. The other 2^24 is a
thrown away 24bit random.

 That is not to say that I don't think you will have  2^76 (ECC)work
 required to break it, taking longer than 2^76 (ECC)work, but that I
 disagree
 with your result. If you set your target at 2^80 (ECC)work, then I believe
 you can achieve it this way. I also think that if you were to perform
 result[i] = hash(result[i-1], passphrase) (result[0] = 0x000...000) it is a
 safe assumption that there is no faster way than counting to i, which would
 vastly improve your chances of security (see Secure Applications of
 Low-Entropy Keys by Hall, Kelsey, Schneier and Wagner for reference). I
 also think that most users would be unwilling to wait the full day you
 spec'd, it is hard enough to get users to wait 5 seconds.

The parameters can be changed as needed. A day can be ok for one
purpose, e.g. for key recovery, while it is not ok for a different
purpose, e.g. recreation of the private key for each decryption. In the
later case the passphrase has to contain more entropy.

Regarding passphrase entropy: Getting entropy into a rememberable
passphrase is a related, but completely different problem.

Matthias

-- 
Matthias Bruestle, Managing Director
Phone +49 (0) 91 19 55 14 91, Fax +49 (0) 91 19 55 14 97
MaskTech GmbH, Nordostpark 16, 90411 Nuernberg, Germany

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Private Key Generation from Passwords/phrases

2007-01-22 Thread Leichter, Jerry
| ...One sometimes sees claims that increasing the salt size is important.
| That's very far from clear to me.  A collision in the salt between
| two entries in the password file lets you try each guess against two
| users' entries.  Since calculating the guess is the hard part,
| that's a savings for the attacker.  With 4K possible salts, you'd need a
| very large password file to have more than a very few collisions,
| though.  It's only a benefit if the password file (or collection of
| password files) is very large.
I've heard of one alleged case, over 20 years ago, of what appeared to
be an actual collision in Unix hashed passwords.  Some undergrads at
Yale somehow came into possession of the root password on the department
Unix server.  The story - I wasn't directly involved and can't vouch
for the details - was that one of the students involved noticed that
his hashed password exactly matched the root hashed password - including
the salt, of course.

It's interesting to look at some of the issues here.  The chance of a
matching pair of passwords *somewhere* gets you into birthday paradox
territory, so isn't all that unlikely; in fact, across the population
of Unix systems, even then, it was probably close to a certainty.  Of
course, knowing that two unspecified users, perhaps in distinct domains,
have the same hashed password, is not generally very useful.  The
chance of a match *with a particular user* - and of course root is the
user of greatest interest, though there would likely be other users
involved in administration whose passwords would be almost as useful
to know - is much less likely (linear as opposed to quadratic), and is
a possibility that is usually ignored:  If I know that root's hashed
password matched that of some user on another machine, what do I do
with that information?  Well ... in a university setting, I might
well be able to approach that other person and, especially in a more
innocent time, get him to share his password with me.

Even so, the probabilities are likely against me.  But I, again in the
world of 20+ years ago, there was another factor:  Dictionary attacks
were not considered plausible at the time, so there was little reason
to choose what we would today consider good passwords.  As I recall,
the root passwords on the Yale machines at that time were words - in
fact, names of ocean creatures.  (I think the compromised password was
dolphin.)  Since students were also probaby choosing words from the
dictionary - and, within the confines of a single department at a single
school at a single time, were probably much more likely than random
chance would predict to pick the same word, as the same concepts and
words were in the shared air - the  effective search space was immensely 
smaller than that implied by the hashed password size.  In this setting,
the chance dictionary search becomes at least plausible.

A great illustration of the need to consider the full system setting!
(Note that against this particular attack, a considerably larger
salt would have been quite effective at little cost.)

-- Jerry

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Private Key Generation from Passwords/phrases

2007-01-21 Thread Steven M. Bellovin
On Sat, 20 Jan 2007 18:41:34 -0600
Travis H. [EMAIL PROTECTED] wrote:

 
 BTW, dictionary attacks can probably be effectively resisted by
 making the hashes of passwords twice as big, and using a random value
 concatenated with the password before hashing, and storing it
 alongside the hash (it's like crypt(3) salting, but more so).  If the
 password is important to keep from disclosure beyond the needs of
 this security system, one could even truncate the output of the hash
 to half its size, so that there's multiple preimages; since you
 doubled the hash size to begin with, you end up with the same
 security factor against guessing, I believe.

Could you explain this?  It's late, but this makes no sense at all to
me.  Dictionary attacks work by guessing -- if the random salt is
visible to the attacker, I don't know what more so might mean.
Similarly, the size of the output is irrelevant; we're not talking
about cryptanalysis here.  As best I can tell, increasing the output
size and/or the salt size increases the size of a precomputed
dictionary, but that's not the only form of dictionary attack -- see M.
Bishop, ?An Application of a Fast Data Encryption Standard
Implementation,? Computing Systems 1(3) pp. 221?254 (Summer 1988), for
example.

One sometimes sees claims that increasing the salt size is important.
That's very far from clear to me.  A collision in the salt between
two entries in the password file lets you try each guess against two
users' entries.  Since calculating the guess is the hard part,
that's a savings for the attacker.  With 4K possible salts, you'd need a
very large password file to have more than a very few collisions,
though.  It's only a benefit if the password file (or collection of
password files) is very large.

There is also some benefit if the attacker is precomputing
dictionaries, but there the size of the search space is large enough
that the salt factor isn't that important given even minimal quality
checks.


 --Steve Bellovin, http://www.cs.columbia.edu/~smb

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Private Key Generation from Passwords/phrases

2007-01-21 Thread Travis H.
On Sun, Jan 21, 2007 at 12:13:09AM -0500, Steven M. Bellovin wrote:
 Could you explain this?  It's late, but this makes no sense at all to
 me.

I probably wasn't clear, you bring out my realization that there
are a number of unwritten assumptions going on here.

 Similarly, the size of the output is irrelevant; we're not talking
 about cryptanalysis here.

Well, I can't disagree, since I also approved of truncating it to
its original size, but I wouldn't want to induce collisions by
making the salted input space much larger than the output space,
or else the work factor goes down for the attacker, right?

 that's not the only form of dictionary attack -- see M.
 Bishop, ?An Application of a Fast Data Encryption Standard
 Implementation,? Computing Systems 1(3) pp. 221?254 (Summer 1988), for
 example.

I'll have to look at that.

 With 4K possible salts, you'd need a
 very large password file to have more than a very few collisions,
 though.  It's only a benefit if the password file (or collection of
 password files) is very large.

Well, birthday paradox here, but what you say is true.  IIRC, standard
cracker practice back when tftp'ing password files was popular was to
pool them all and sort by salt, then computing the most common salts
and the most common passwords.

 There is also some benefit if the attacker is precomputing
 dictionaries, but there the size of the search space is large enough
 that the salt factor isn't that important given even minimal quality
 checks.

Really?  What about rainbow tables?  I heard recently that there was a
relatively complete MD5 rainbow table online with an ajax/js interface
for searching it.  Unless I'm missing something obvious, this basically
eliminates the advantage of hashing unsalted passwords with MD5 to null.

I look favorably on the formats that allow you to iterate a OWF over
the password N times, and that store N in the entry.  That way, if the
costs of running the algorithm go down, you can just increase the
number of times it has been run on every entry in the file without
requiring any interaction from end-users.  This kind of scaling with
the world is needed, because cryptanalysis isn't a stagnant field, and
Moore's Law still holds, and I find the idea of having to change
between incompatible systems just to keep the same level of security,
and on someone else's schedule, to be undesirable.
-- 
``Unthinking respect for authority is the greatest enemy of truth.''
-- Albert Einstein -- URL:http://www.subspacefield.org/~travis/


pgpI8slDM82ce.pgp
Description: PGP signature


Re: Private Key Generation from Passwords/phrases

2007-01-20 Thread Travis H.
On Fri, Jan 19, 2007 at 12:11:40AM -0800, Bill Stewart wrote:
 One of the roots of the problem is that for many applications,
 i is a well-defined event and P(i) is a fixed value (for i) ,
 but for many other applications,
 i might not be a well-defined event, and/or
 P(i) is really a conditional probability, P(i|other-stuff-you-know),
 and it's hard to tell whether that's
 usefully different from the non-conditional P(i).

Yes; in textbooks, the author is usually kind enough to give a
complete description of the source; in cryptanalysis, you're usually
looking at the output and making inferences about the source, and
thus, the entropy.

 Another entropy example was the Venona decryptions -
 people banging randomly on typewriters didn't actually produce
 independent or identically distributed letters,
 so the conditional probabilities didn't actually match
 the assumed ones, so the entropy estimates were wrong,
 and human language plaintext being what it is,
 they really needed the 1-bit-per-bit of key entropy.

Actually, my reading of a book on Venona said they captured some
unused OTP on microfilm, but weren't able to use the non-randomness of
the source to decrypt anything.  Someone here mentioned that the
entropy of the plaintext and the OTP have to merely add to 1 to
prevent decryption; the OTP does not necessarily have to provide it
all.  Shannon's estimates were that English prose carries about 1 bit
per symbol.

There were some decrypts of material; the official explanation is that
they recovered a partial codebook and discovered some OTP re-use (the
KGB encoded then superenciphered it).

BTW, dictionary attacks can probably be effectively resisted by
making the hashes of passwords twice as big, and using a random value
concatenated with the password before hashing, and storing it alongside
the hash (it's like crypt(3) salting, but more so).  If the password is
important to keep from disclosure beyond the needs of this security
system, one could even truncate the output of the hash to half its size,
so that there's multiple preimages; since you doubled the hash size to
begin with, you end up with the same security factor against guessing,
I believe.
-- 
``Unthinking respect for authority is the greatest enemy of truth.''
-- Albert Einstein -- URL:http://www.subspacefield.org/~travis/


pgpJoxUCemN6j.pgp
Description: PGP signature


Re: Private Key Generation from Passwords/phrases

2007-01-19 Thread Bill Stewart

At 01:55 PM 1/18/2007, John Denker wrote:

We would be better off maintaining just the one technical
definition of entropy, namely S = sum_i P_i log(1/P_i).
If you want to talk about something else, call it something
else ... or at least make it clear that you are using the
term in a nontechnical or metaphorical sense.
...
If you want to talk about work factor, call it work factor.
If you want to talk about entropy, call it entropy.


One of the roots of the problem is that for many applications,
i is a well-defined event and P(i) is a fixed value (for i) ,
but for many other applications,
i might not be a well-defined event, and/or
P(i) is really a conditional probability, P(i|other-stuff-you-know),
and it's hard to tell whether that's
usefully different from the non-conditional P(i).

One case where this comes up is key generation with entropy pools -
you take a bunch of hopefully-kinda-independent,
hopefully-identically-distributed variables generated
by processes that are complicated enough to look random,
make some estimates of their probability distributions
and hence of their entropy, and add the estimates together,
after prewhitening the samples to make any correlation
harder to exploit.  This gives you N bits of entropy,
and you take M bits of it to use as a key,
again possibly with some hash functions to make
calculations more difficult.

So how many bits of entropy are left?
You can be conservative and call it N-M,
assuming that if somebody were clever enough to take
the M bits key sample they could validate the rest
with only N-M calls to an oracle,
or you could be wildly optimistic and call it N,
assuming that the conditional probabilities of the
remaining pool are still the same given that you know the M bits,
because there's no way to use them to validate anything,
and if you've done a good enough job of designing your
pool management functions the reality is probably
closer to the wildly optimistic case,
unless somebody finds an efficient way to invert your hash functions,
at which point the conditional probabilities are actually
different if you know the M key bits than if you don't.

Another entropy example was the Venona decryptions -
people banging randomly on typewriters didn't actually produce
independent or identically distributed letters,
so the conditional probabilities didn't actually match
the assumed ones, so the entropy estimates were wrong,
and human language plaintext being what it is,
they really needed the 1-bit-per-bit of key entropy.
It's much tougher to exploit than OTPs used more than once,
but it's a start.

But hey, nobody's going to guess that your password
is your dog's name spelled backwards, or think of using
a list of a few million obvious passwords as input to
the key-generation function.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Private Key Generation from Passwords/phrases

2007-01-18 Thread Allen

Joseph,

The whole issue of entropy is a bit vague for me - I don't 
normally work at that end of things - so could you point to a 
good tutorial on the subject, or barring having a reference 
handy, could you give an overview?


Thanks,

Allen

Joseph Ashwood wrote:
- Original Message - From: Matthias Bruestle 
[EMAIL PROTECTED]

Subject: Private Key Generation from Passwords/phrases



What do you think about this?


I think you need some serious help in learning the difference between 
2^112 and 112, and that you really don't seem to have much grasp of the 
entire concept. 112 bits of entropy is 112 bits of entropy, not 76 bits 
of entropy, 27 bits of bull, 7 bits of cocaine, and a little bit of 
alcohol, and the 224 bits of ECC is approximate anyway, as you noted the 
time units are inconsistent. Basically just stop fiddling around trying 
to convince yourself you need less than you do, and locate 112 bits of 
apparent entropy, anything else and you're into the world of trying to 
prove equivalence between entropy and work which work in physics but 
doesn't work in computation because next year the work level will be 
different and you'll have to redo all your figures.

   Joe

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]




-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Private Key Generation from Passwords/phrases

2007-01-18 Thread Perry E. Metzger

John Denker [EMAIL PROTECTED] writes:
 There is only one technical definition of entropy,

Oh?

So you're saying Chaitin-Kolmogrov information and other ways of
studying entropy are wrong? I think that's a bit unreasonable, don't
you?

There are different definitions that are useful at different
times. Fundamentally, mathematics provides us with models, which are
sometimes applicable to a particular practical problem, and sometimes
are not applicable. It is dangerous to forget that. When you do, you
get things like proofs of security based on inapplicable models, and
worse.

Perry

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Private Key Generation from Passwords/phrases

2007-01-16 Thread Matthias Bruestle
Joseph Ashwood wrote:
 - Original Message - From: Matthias Bruestle
 [EMAIL PROTECTED]
 
 What do you think about this?
 
 I think you need some serious help in learning the difference between
 2^112 and 112, and that you really don't seem to have much grasp of the
 entire concept.

Please omit all 2^ besides in the 2^24. This should make you feel
better.

 [most offensive parts deleted]
 time units are inconsistent. Basically just stop fiddling around trying
 to convince yourself you need less than you do, and locate 112 bits of
 apparent entropy, anything else and you're into the world of trying to
 prove equivalence between entropy and work which work in physics but
 doesn't work in computation because next year the work level will be
 different and you'll have to redo all your figures.

What we are interested in is time (e.g. secure until 20XX), not
entropy. After all we are all in a physical world, also the computers.
But for entropy we can buy time. Because physical world changes things
have to be redone, e.g. DES - 3DES - AES - ... . So 30 years ago a
bit of entropy bought you much time, now not so much anymore. But
despite that with the system described in my email the figures don't
have to be redone every year. Because the computers (in the physical
world) get faster each year the time to bruteforce 3DES and 224bit-ECC
gets lower. The relation stays (mostly) the same. The only thing which
really changes is the time a user has to wait for recreating his key,
which gets lower and lower. He certainly has no problem with that.

Maybe you should take James Donald as an inspiring example for you. He
raised a valid point, the offline attack using the generally available
public key.

Matthias

-- 
Matthias Bruestle, Managing Director
Phone +49 (0) 91 19 55 14 91, Fax +49 (0) 91 19 55 14 97
MaskTech GmbH, Nordostpark 16, 90411 Nuernberg, Germany

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Private Key Generation from Passwords/phrases

2007-01-16 Thread [EMAIL PROTECTED]

On 1/11/07, Joseph Ashwood [EMAIL PROTECTED] wrote:


112 bits of entropy is 112 bits of entropy...anything else and you're
into the world of trying to prove equivalence between entropy and
work which work in physics but doesn't work in computation
because next year the work level will be different and you'll
have to redo all your figures.


Hmm. All we usually have protecting us is work.

Once a little bit of cipher text gets out, on an SSL session or a PGP
encrypted email or the like, that bit of cipher text is enough
information to unambiguously determine the key. It may take a lot of
work to determine the key but there is no uncertainty left in the key.
That is, once used for a bit of encrypting where the cipher text
becomes known, the entropy of that key is _zero_.

Since there is no unguessibility left in the key, the only thing
protecting the cipher text is the amount of work it takes to determine
the key.

It seems Matthias has realized, prudently, that his system has a weak
link at the passphrase and he is looking to strengthen that. The ways
to do that include requiring a ridiculously long passphrase or
increasing the work required to go from the passphrase to the key.
Both methods Matthias has chosen increase the work required to break
the system.

As James pointed out, the proposed 76-bit passphrase is a bit much to
expect anybody to remember and it is always better to not derive keys
from passwords when the system allows.

-Michael Heyman

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Private Key Generation from Passwords/phrases

2007-01-13 Thread Joseph Ashwood
- Original Message - 
From: Matthias Bruestle [EMAIL PROTECTED]

Subject: Private Key Generation from Passwords/phrases



What do you think about this?


I think you need some serious help in learning the difference between 2^112 
and 112, and that you really don't seem to have much grasp of the entire 
concept. 112 bits of entropy is 112 bits of entropy, not 76 bits of entropy, 
27 bits of bull, 7 bits of cocaine, and a little bit of alcohol, and the 224 
bits of ECC is approximate anyway, as you noted the time units are 
inconsistent. Basically just stop fiddling around trying to convince 
yourself you need less than you do, and locate 112 bits of apparent entropy, 
anything else and you're into the world of trying to prove equivalence 
between entropy and work which work in physics but doesn't work in 
computation because next year the work level will be different and you'll 
have to redo all your figures.
   Joe 



-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Private Key Generation from Passwords/phrases

2007-01-13 Thread James A. Donald

Matthias Bruestle wrote:

Hi,

I am thinking about this since last night. On the web I haven't found
much and I want to go in a different direction as I have found.

Say I want to have 112bit security, i.e. as secure as 3DES. For this I
would choose (as everybody writes) 224bit ECC (or Tipsy Curve
Cryptosystem/TCC as I prefer, because the European Citizen Card is also
called ECC officially). With the Passwords I would have to provide so
much entropy, that a bruteforce attack needs as much time as 3DES to get
the same security. (Higher value of ECC key ignored.)

When I look at benchmarks ratio of the number of 3DES operations and of
point multiplications is about 4000:1, so I have gained here about 2^12
bits. (Processing of Password with a hash function is so fast that it
can be ignored unless the procession is artificially extended.) I am
aware that a DES unit is cheaper than an ECC unit and that for DES there
are special implementations for key search possible, so the gain might
be even more.

Lets assume the key is only very seldom regenerated. Then we could add a
short fragment of real entropy to the passwords and throw it away after
our first key generation. If a point multiplication takes around 4ms
then we can brute force on one day 2^24 keys. So if the user is willing
to wait for one day for his key recreation than he can add 3 random
bytes to his passwords and throw them away.

If we add this together, than we have already 2^36 bits of security from
our goal of 2^112 bits. The remaining necessary entropy is then 2^76
bits which would have then to be provided by the passwords/phrase. That
means the necessary length is reduced by about one third.

What do you think about this?


You are not going to get 76 bits of entropy in a password.

Memorizing a 76 bit password is equivalent to memorizing three seven 
digit telephone numbers.


Assume that the private key is generated from the password plus an n bit 
true random number.


To regenerate the private key we have to try 2^n private keys, looking 
for a match to the public key.  Assume this takes time X.


Assume the actual entropy in the password is m bits.  Then an attacker 
who has similar computing resources is going to take time X * 2^m


Any time a password can be subject to offline attack by anyone, it is 
not a good design.  You are better off fixing it so that only certain 
people can offline attack the password, and everyone else has to do an 
online attack on the passwrod.


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Private Key Generation from Passwords/phrases

2007-01-11 Thread Matthias Bruestle
Hi,

I am thinking about this since last night. On the web I haven't found
much and I want to go in a different direction as I have found.

Say I want to have 112bit security, i.e. as secure as 3DES. For this I
would choose (as everybody writes) 224bit ECC (or Tipsy Curve
Cryptosystem/TCC as I prefer, because the European Citizen Card is also
called ECC officially). With the Passwords I would have to provide so
much entropy, that a bruteforce attack needs as much time as 3DES to get
the same security. (Higher value of ECC key ignored.)

When I look at benchmarks ratio of the number of 3DES operations and of
point multiplications is about 4000:1, so I have gained here about 2^12
bits. (Processing of Password with a hash function is so fast that it
can be ignored unless the procession is artificially extended.) I am
aware that a DES unit is cheaper than an ECC unit and that for DES there
are special implementations for key search possible, so the gain might
be even more.

Lets assume the key is only very seldom regenerated. Then we could add a
short fragment of real entropy to the passwords and throw it away after
our first key generation. If a point multiplication takes around 4ms
then we can brute force on one day 2^24 keys. So if the user is willing
to wait for one day for his key recreation than he can add 3 random
bytes to his passwords and throw them away.

If we add this together, than we have already 2^36 bits of security from
our goal of 2^112 bits. The remaining necessary entropy is then 2^76
bits which would have then to be provided by the passwords/phrase. That
means the necessary length is reduced by about one third.

What do you think about this?

Matthias

-- 
Matthias Bruestle, Managing Director
Phone +49 (0) 91 19 55 14 91, Fax +49 (0) 91 19 55 14 97
MaskTech GmbH, Nordostpark 16, 90411 Nuernberg, Germany

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]