Re: Private Key Generation from Passwords/phrases
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
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
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
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
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
Matthias Bruestle wrote: [snip] Regarding passphrase entropy: Getting entropy into a rememberable passphrase is a related, but completely different problem. Here might be a screwy way of increasing the entropy of a passphrase while still allowing it to be readable/memorization. At Cambridge a number of years ago they were doing readability studies and out of it came the following funny quote: I cdnuolt blveiee taht I cluod aulaclty uesdnatnrd waht I was rdenaig. The phonemneal pweor of the hmuan mnid ! Aodccrnig to rserceah at Cmabrigde Uinervtisy, it dnsoe't mttaer in waht oredr the ltteers in a wrod are, the olny iprmoatnt tihng is taht the frist and lsat ltteer be in the rghit pclae. The rset can be a taotl mses and you can sitll raed it wouthit a porbelm. Tihs is bcuseae the hmuan mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe. Azmanig huh? Yaeh and I awlyas tghuoht slpeling was ipmrtnoat. Well, it sure messes with any dictionary based attack. :) Best, Allen - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Private Key Generation from Passwords/phrases
> 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]
Re: Private Key Generation from Passwords/phrases
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
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. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Private Key Generation from Passwords/phrases
| ...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
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 -><- http://www.subspacefield.org/~travis/> pgpI8slDM82ce.pgp Description: PGP signature
Re: Private Key Generation from Passwords/phrases
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
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 -><- http://www.subspacefield.org/~travis/> pgpJoxUCemN6j.pgp Description: PGP signature
Re: Private Key Generation from Passwords/phrases
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
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
On 01/18/2007 03:13 PM, David Wagner wrote: > In article <[EMAIL PROTECTED]> you write: >> The /definition/ of entropy is >> >> sum_i P_i log(1/P_i) [1] >> >> there the sum runs over all symbols (i) in the probability >> distribution, i.e. over all symbols in the ensemble. >> >> Equation [1] is the gold standard. It is always correct. Any >> other expression for entropy is: >> a) equivalent to [1] >> b) a corollary, valid under some less-than-general conditions, or >> c) wrong. > > I disagree. In the context of Physics, Shannon entropy may well be > the end-all and be-all of entropy measures, but in the context of > Cryptography, the situation is a little different. In Cryptography, > there are multiple notions of entropy, and they're each useful in > different situations. There is only one technical definition of entropy, and only one technical definition of force, and only one technical definition definition of power. In parallel, there are nontechnical and metaphorical uses of the same words, as in "military force" and "political power". 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. > For this particular application, I would suspect that Pliam's workfactor > or Massey's "guessing entropy" could well be more accurate. See, e.g., > the following for a short summary and for references where you can learn > more: > http://www.cs.berkeley.edu/~daw/my-posts/entropy-measures Pliam rightly points out the distinction between the "typical" case and the "average" case. Entropy is an /average/ property, as I emphasized in my note this morning. > Shannon entropy is often a reasonable first approximation -- it's > usually good enough for practical purposes. But it's just an approximation, An approximation to what? It's not an approximation to the entropy. > and in some cases it can be misleading. As a general rule, /anything/ can be abused. > Example: Suppose I choose a random 256-bit AES key according to the > following distribution. With probability 1/2, I use the all-zeros key. > Otherwise, I choose a random 256-bit key. OK. > The Shannon entropy of this > distribution is approximately 129 bits. Yes. > However, it's a lousy way to > choose a key, because 50% of the time an adversary can break your > crypto immediately. In other words, just because your crypto key has > 129 bits of Shannon entropy doesn't mean that exhaustive keysearch will > require at least 2^129 trial decryptions. This is one (contrived) > example where the Shannon entropy can be misleading. I never said the entropy was equal to the resistance to guessing. The crypto FAQ might have said that at one time ... but I am not responsible for what other people say. I am only responsible for what I say. If you want to talk about work factor, call it work factor. If you want to talk about entropy, call it entropy. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Private Key Generation from Passwords/phrases
On 01/17/2007 06:07 PM, Allen wrote: > 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? Entropy is defined in terms of probability. The /definition/ of entropy is sum_i P_i log(1/P_i) [1] there the sum runs over all symbols (i) in the probability distribution, i.e. over all symbols in the ensemble. Equation [1] is the gold standard. It is always correct. Any other expression for entropy is: a) equivalent to [1] b) a corollary, valid under some less-than-general conditions, or c) wrong. We have not yet specified the _base_ of the log in equation [1]. If the log is base 2, the entropy is measured in bits. If the log is base 3, the entropy is measured in nats. For more on this, including the connection to macroscopic thermodynamics, see http://www.av8n.com/physics/thermo-laws.htm#sec-s-units One toss of a fair coin is 1 bit of entropy. Two tosses of a fair coin is 2 bits of entropy. Entropy can be measured in bits, but not everything measured in bits is entropy (just as milk can be measured in gallons, but also sewage can be measured in gallons). In particular, a 32 bit word may hold less than 32 bits of entropy, but it cannot hold more. A related notion is the /surprise value/ of a given symbol, namely $_i = log(1/P_i) We immediately see that the entropy is the appropriately weighted average of the surprise value. It must be emphasize that entropy is a property of the whole ensemble (in contrast to the surprise value which is a property of an individual symbol). There is no such thing as the "average entropy"; entropy is already an average. There are two branches of cryptography. -- One branch depends on entropy for security. -- The other branch depends on computational complexity for security. The term /random/ is used in multiple inconsistent ways; if you ask 5 experts you can get 10 different definitions. As for me, I say something is random if it is _random enough for the application_. I am *not* correspondingly tolerant about the term entropy. Entropy is entropy. There is only one definition of entropy, used uniformly across a wide range of disciplines including 1. cryptography and cryptanalysis (secret codes) 2. communications (error-correcting codes, as part of electronic engineering) 3. computer science, including data-compression codes, machine learning, speech recognition, etc. 4. librarianship 5. the physics of computation 6. the design of refrigerators, heat pumps, and engines (including piston, turbine, and rocket engines) 7. nuclear engineering (reactors and weapons) 8. fluid dynamics 9. astrophysics and cosmology 10. chemistry and chemical engineering If you're not defining it in terms of equation [1] or something provably equivalent, don't call it entropy. In particular, 200 bits of pseudorandomness is not the same as 200 bits of entropy. If you mean entropy, say entropy; if you mean randomness, say randomness. Sometimes pseudorandomness based on computational complexity is suitable for the application, and sometimes it doesn't make sense to use anything less than genuine entropy. For more on how to generate usable entropy, see http://www.av8n.com/turbid/paper/turbid.htm For more about the definition of entropy, including the connection to thermodynamics, see http://www.av8n.com/physics/thermo-laws.htm#sec-entropy - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Private Key Generation from Passwords/phrases
I'm going to try to make this one a bit less aggregious in tone. I'm also going to sometimes use (3DES) and (ECC) for designation of work and time measurements. - Original Message - From: "Matthias Bruestle" <[EMAIL PROTECTED]> Cc: Sent: Monday, January 15, 2007 2:31 AM Subject: Re: Private Key Generation from Passwords/phrases Joseph Ashwood wrote: - Original Message - From: "Matthias Bruestle" <[EMAIL PROTECTED]> [most offensive parts deleted] 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. 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. 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. 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. Joe - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Private Key Generation from Passwords/phrases
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
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
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
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]
Re: Private Key Generation from Passwords/phrases
- 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]
