Re: [Cryptography] please dont weaken pre-image resistance of SHA3 (Re: NIST about to weaken SHA3?)
Adam,
I guess I should preface this by saying I am speaking only for myself. That's
always true here--it's why I'm using my personal email address. But in
particular, right now, I'm not *allowed* to work. But just speaking my own
personal take on things
We go pretty *overwhelming* feedback in this direction in the last three weeks.
(For the previous several months, we got almost no feedback about it at all,
despite giving presentations and posting stuff on hash forum about our plans.).
But since we're shut down right now, we can't actually make any decisions or
changes. This is really frustrating on all kinds of levels.
Personally, I have looked at the technical arguments against the change and I
don't really find any of them very convincing, for reasons I described at some
length on the hash forum list, and that the Keccak designers also laid out in
their post. The core of that is that an attacker who can't do 2^{128} work
can't do anything at all to SHA3 with a 256 bit capacity that he couldn't also
do to SHA3 with a 512 bit capacity, including finding preimages.
But there's pretty much zero chance that we're going to put a standard out that
most of the crypto community is uncomfortable with. The normal process for a
FIPS is that we would put out a draft and get 60 or 90 days of public comments.
As long as this issue is on the table, it's pretty obvious what the public
comments would all be about.
The place to go for current comments, if you think more are necessary, is the
hash forum list. The mailing list is still working, but I think both the
archives and the process of being added to the list are frozen thanks to the
shutdown. I haven't looked at the hash forum since we shut down, so when we
get back there will be a flood of comments there. The last I saw, the Keccak
designers had their own proposal for changing what we put into the FIPS, but I
don't know what people think about their proposal.
--John, definitely speaking only for myself
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Crypto Standards v.s. Engineering habits - Was: NIST about to weaken SHA3?
On Oct 12, 2013, at 6:51 AM, Ben Laurie b...@links.org wrote: ... AIUI, you're trying to make it so that only active attacks work on the combined protocol, whereas passive attacks might work on the outer protocol. In order to achieve this, you assume that your proposed inner protocol is not vulnerable to passive attacks (I assume the outer protocol also thinks this is true). Why should we believe the inner protocol is any better than the outer one in this respect? The point is, we don't know how to make protocols that really are reliably secure against future attacks. If we did, we'd just do that. My hope is that if we layer two of our best attempts at secure protocols on top of one another, then we will get security because the attacks will be hard to get through the composed protocols. So maybe my protocol (or whatever inner protocol ends up being selected) isn't secure against everything, but as long as its weaknesses are covered up by the outer protocol, we still get a secure final result. One requirement for this is that the inner protocol must not introduce new weaknesses. I think that means it must not: a. Leak information about its plaintexts in its timing, error messages, or ciphertext sizes. b. Introduce ambiguities about how the plaintext is to be decrypted that could mess up the outer protocol's authentication. I think we can accomplish (a) by not compressing the plaintext before processing it, by using crypto primitives that don't leak plaintext data in their timing, and by having the only error message that can ever be generated from the inner protocol be essentially a MAC failure or an out-of-sequence error. I think (b) is pretty easy to accomplish with standard crypto, but maybe I'm missing something. ... Particularly since you're using tainted algorithms ;-). If using AES or P256 are the weak points in the protocol, that is a big win. Right now, we aren't getting anywhere close to that. And there's no reason either AES or P256 have to be used--I'm just looking for a simple, lightweight way to get as much security as possible inside some other protocol. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Crypto Standards v.s. Engineering habits - Was: NIST about to weaken SHA3?
On Oct 11, 2013, at 1:48 AM, ianG i...@iang.org wrote: ... What's your goal? I would say you could do this if the goal was ultimate security. But for most purposes this is overkill (and I'd include online banking, etc, in that). We were talking about how hard it is to solve crypto protocol problems by getting the protocol right the first time, so we don't end up with fielded stuff that's weak but can't practically be fixed. One approach I can see to this is to have multiple layers of crypto protocols that are as independent as possible in security terms. The hope is that flaws in one protocol will usually not get through the other layer, and so they won't lead to practical security flaws. Actually getting the outer protocol right the first time would be better, but we haven't had great success with that so far. Right now we've got a TCP startup, and a TLS startup. It's pretty messy. Adding another startup inside isn't likely to gain popularity. Maybe not, though I think a very lightweight version of the inner protocol adds only a few bits to the traffic used and a few AES encryptions to the workload. I suspect most applications would never notice the difference. (Even the version with the ECDH key agreement step would probably not add noticable overhead for most applications.) On the other hand, I have no idea if anyone would use this. I'm still at the level of thinking what could be done to address this problem, not how would you sell this? iang --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Key stretching
This is a job for a key derivation function or a cryptographic prng. I would use CTR-DRBG from 800-90 with AES256. Or the extract-then-expand KDF based on HMAC-SHA512. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Iran and murder
The problem with offensive cyberwarfare is that, given the imbalance between attackers and defenders and the expanding use of computer controls in all sorts of systems, a cyber war between two advanced countries will not decide anything militarily, but will leave both combattants much poorer than they were previously, cause some death and a lot of hardship and bitterness, and leave the actual hot war to be fought. Imagine a conflict that starts with both countries wrecking a lot of each others' infrastructure--causing refineries to burn, factories to wreck expensive equipment, nuclear plants to melt down, etc. A week later, that phase of the war is over. Both countries are, at that point, probalby 10-20% poorer than they were a week earlier. Both countries have lots of really bitter people out for blood, because someone they care about was killed or their job's gone and their house burned down or whatever. But probably there's been little actual degradation of their standard war-fighting ability. Their civilian aviation system may be shut down, some planes may even have been crashed, but their bombers and fighters and missiles are mostly still working. Fuel and spare parts may be hard to come by, but the military will certainly get first pick. My guess is that what comes next is that the two countries have a standard hot war, but with the pleasant addition of a great depression sized economic collapse for both right in the middle of it. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Crypto Standards v.s. Engineering habits - Was: NIST about to weaken SHA3?
Just thinking out loud The administrative complexity of a cryptosystem is overwhelmingly in key management and identity management and all the rest of that stuff. So imagine that we have a widely-used inner-level protocol that can use strong crypto, but also requires no external key management. The purpose of the inner protocol is to provide a fallback layer of security, so that even an attack on the outer protocol (which is allowed to use more complicated key management) is unlikely to be able to cause an actual security problem. On the other hand, in case of a problem with the inner protocol, the outer protocol should also provide protection against everything. Without doing any key management or requiring some kind of reliable identity or memory of previous sessions, the best we can do in the inner protocol is an ephemeral Diffie-Hellman, so suppose we do this: a. Generate random a and send aG on curve P256 b. Generate random b and send bG on curve P256 c. Both sides derive the shared key abG, and then use SHAKE512(abG) to generate an AES key for messages in each direction. d. Each side keeps a sequence number to use as a nonce. Both sides use AES-CCM with their sequence number and their sending key, and keep track of the sequence number of the most recent message received from the other side. The point is, this is a protocol that happens *inside* the main security protocol. This happens inside TLS or whatever. An attack on TLS then leads to an attack on the whole application only if the TLS attack also lets you do man-in-the-middle attacks on the inner protocol, or if it exploits something about certificate/identity management done in the higher-level protocol. (Ideally, within the inner protcol, you do some checking of the identity using a password or shared secret or something, but that's application-level stuff the inner and outer protocols don't know about. Thoughts? --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] prism-proof email in the degenerate case
Having a public bulletin board of posted emails, plus a protocol for anonymously finding the ones your key can decrypt, seems like a pretty decent architecture for prism-proof email. The tricky bit of crypto is in making access to the bulletin board both efficient and private. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Crypto Standards v.s. Engineering habits - Was: NIST about to weaken SHA3?
More random thoughts: The minimal inner protocol would be something like this: Using AES-CCM with a tag size of 32 bits, IVs constructed based on an implicit counter, and an AES-CMAC-based KDF, we do the following: Sender: a. Generate random 128 bit value R b. Use the KDF to compute K[S],N[S],K[R],N[R] = KDF(R, 128+96+128+96) c. Sender's 32-bit unsigned counter C[S] starts at 0. d. Compute IV[S,0] = 96 bits of binary 0s||C[S] e. Send R, CCM(K[S],N[S],IV[S,0],sender_message[0]) Receiver: a. Receive R and derive K[S],N[S],K[R],N[R] from it as above. b. Set Receiver's counter C[R] = 0. c. Compute IV[R,0] = 96 bits of binary 0s||C[R] d. Send CCM(K[R],N[R],IV[R,0],receiver_message[0]) and so on. Note that in this protocol, we never send a key or IV or nonce. The total communications overhead of the inner protocol is an extra 160 bits in the first message and an extra 32 bits thereafter. We're assuming the outer protocol is taking care of message ordering and guaranteed delivery--otherwise, we need to do something more complicated involving replay windows and such, and probably have to send along the message counters. This doesn't provide a huge amount of extra protection--if the attacker can recover more than a very small number of bits from the first message (attacking through the outer protocol), then the security of this protocol falls apart. But it does give us a bare-minimum-cost inner layer of defenses, inside TLS or SSH or whatever other thing we're doing. Both this and the previous protocol I sketched have the property that they expect to be able to generate random numbers. There's a problem there, though--if the system RNG is weak or trapdoored, it could compromise both the inner and outer protocol at the same time. One way around this is to have each endpoint that uses the inner protocol generate its own internal secret AES key, Q[i]. Then, when it's time to generate a random value, the endpoint asks the system RNG for a random number X, and computes E_Q(X). If the attacker knows Q but the system RNG is secure, we're fine. Similarly, if the attacker can predict X but doesn't know Q, we're fine. Even when the attacker can choose the value of X, he can really only force the random value in the beginning of the protocol to repeat. In this protocol, that doesn't do much harm. The same idea works for the ECDH protocol I sketched earlier. I request two 128 bit random values from the system RNG, X, X'. I then use E_Q(X)||E_Q(X') as my ephemeral DH private key. If an attacker knows Q but the system RNG is secure, then we get an unpredictable value for the ECDH key agreement. If an attacker knows X,X' but doesn't know Q, he doesn't know what my ECDH ephemeral private key is. If he forces it to a repeated value, he still doesn't weaken anything except this run of the protocol--no long-term secret is leaked if AES isn't broken. This is subject to endless tweaking and improvement. But the basic idea seems really valuable: a. Design an inner protocol, whose job is to provide redundancy in security against attacks on the outer protocol. b. The inner protocol should be: (i) As cheap as possible in bandwidth and computational terms. (ii) Flexible enough to be used extremely widely, implemented in most places, etc. (iii) Administratively free, adding no key management or related burdens. (iv) Free from revisions or updates, because the whole point of the inner protocol is to provide redundant security. (That's part of administratively free.) (v) There should be one or at most two versions (maybe something like the two I've sketched, but better thought out and analyzed). c. As much as possible, we want the security of the inner protocol to be independent of the security of the outer protocol. (And we want this without wanting to know exactly what the outer protocol will look like.) This means: (i) No shared keys or key material or identity strings or anything. (ii) The inner protocol can't rely on the RNG being good. (iii) Ideally, the crypto algorithms would be different, though that may impose too high a cost. At least, we want as many of the likely failure modes to be different. Comments? I'm not all that concerned with the protocol being perfect, but what do you think of the idea of doing this as a way to add redundant security against protocol attacks? --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Crypto Standards v.s. Engineering habits - Was: NIST about to weaken SHA3?
On Oct 10, 2013, at 5:15 PM, Richard Outerbridge ou...@sympatico.ca wrote: How does this prevent MITM? Where does G come from? I'm assuming G is a systemwide shared parameter. It doesn't prevent mitm--remember the idea here is to make a fairly lightweight protocol to run *inside* another crypto protocol like TLS. The inner protocol mustn't add administrative requirements to the application, which means it can't need key management from some administrator or something. The goal is to have an inner protocol which can run inside TLS or some similar thing, and which adds a layer of added security without the application getting more complicated by needing to worry about more keys or certificates or whatever. Suppose we have this inner protocol running inside a TLS version that is subject to one of the CBC padding reaction attacks. The inner protocol completely blocks that. I'm also leery of using literally the same key in both directions. Maybe a simple transform would suffice; maybe not. I probably wasn't clear in my writeup, but my idea was to have different keys in different directions--there is a NIST KDF that uses only AES as its crypto engine, so this is relatively easy to do using standard components. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] prism-proof email in the degenerate case
On Oct 10, 2013, at 5:20 PM, Ray Dillinger b...@sonic.net wrote: On 10/10/2013 12:54 PM, John Kelsey wrote: Having a public bulletin board of posted emails, plus a protocol for anonymously finding the ones your key can decrypt, seems like a pretty decent architecture for prism-proof email. The tricky bit of crypto is in making access to the bulletin board both efficient and private. Wrong on both counts, I think. If you make access private, you generate metadata because nobody can get at mail other than their own. If you make access efficient, you generate metadata because you're avoiding the wasted bandwidth that would otherwise prevent the generation of metadata. Encryption is sufficient privacy, and efficiency actively works against the purpose of privacy. So the original idea was to send a copy of all the emails to everyone. What I'm wanting to figure out is if there is a way to do this more efficiently, using a public bulletin board like scheme. The goal here would be: a. Anyone in the system can add an email to the bulletin board, which I am assuming is public and cryptographically protected (using a hash chain to make it impossible for even the owner of the bulletin board to alter things once published). b. Anyone can run a protocol with the bulletin board which results in them getting only the encrypted emails addressed to them, and prevents the bulletin board operator from finding out which emails they got. This sounds like something that some clever crypto protocol could do. (It's related to the idea of searching on encrypted data.). And it would make an email system that was really resistant to tracing users. Bear --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Crypto Standards v.s. Engineering habits - Was: NIST about to weaken SHA3?
On Oct 8, 2013, at 4:46 PM, Bill Frantz fra...@pwpconsult.com wrote: I think the situation is much more serious than this comment makes it appear. As professionals, we have an obligation to share our knowledge of the limits of our technology with the people who are depending on it. We know that all crypto standards which are 15 years old or older are obsolete, not recommended for current use, or outright dangerous. We don't know of any way to avoid this problem in the future. We know how to address one part of this problem--choose only algorithms whose design strength is large enough that there's not some relatively close by time when the algorithms will need to be swapped out. That's not all that big a problem now--if you use, say, AES256 and SHA512 and ECC over P521, then even in the far future, your users need only fear cryptanalysis, not Moore's Law. Really, even with 128-bit security level primitives, it will be a very long time until the brute-force attacks are a concern. This is actually one thing we're kind-of on the road to doing right in standards now--we're moving away from barely-strong-enough crypto and toward crypto that's going to be strong for a long time to come. Protocol attacks are harder, because while we can choose a key length, modulus size, or sponge capacity to support a known security level, it's not so easy to make sure that a protocol doesn't have some kind of attack in it. I think we've learned a lot about what can go wrong with protocols, and we can design them to be more ironclad than in the past, but we still can't guarantee we won't need to upgrade. But I think this is an area that would be interesting to explore--what would need to happen in order to get more ironclad protocols? A couple random thoughts: a. Layering secure protocols on top of one another might provide some redundancy, so that a flaw in one didn't undermine the security of the whole system. b. There are some principles we can apply that will make protocols harder to attack, like encrypt-then-MAC (to eliminate reaction attacks), nothing is allowed to need change its execution path or timing based on the key or plaintext, every message includes a sequence number and the hash of the previous message, etc. This won't eliminate protocol attacks, but will make them less common. c. We could try to treat at least some kinds of protocols more like crypto algorithms, and expect to have them widely vetted before use. What else? ... Perhaps the shortest limit on the lifetime of an embedded system is the security protocol, and not the hardware. If so, how do we as society deal with this limit. What we really need is some way to enforce protocol upgrades over time. Ideally, there would be some notion that if you support version X of the protocol, this meant that you would not support any version lower than, say, X-2. But I'm not sure how practical that is. Cheers -- Bill --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Sha3
On Oct 6, 2013, at 6:29 PM, Jerry Leichter leich...@lrw.com wrote: On Oct 5, 2013, at 6:12 PM, Ben Laurie wrote: I have to take issue with this: The security is not reduced by adding these suffixes, as this is only restricting the input space compared to the original Keccak. If there is no security problem on Keccak(M), there is no security problem on Keccak(M|suffix), as the latter is included in the former. I also found the argument here unconvincing. After all, Keccak restricted to the set of strings of the form M|suffix reveals that it's input ends with suffix, which the original Keccak did not. The problem is with the vague nature of no security problem. They are talking about the change to their padding scheme, in which between 2 and 4 bits of extra padding are added to the padding scheme that was originally proposed for SHA3. A hash function that works by processing r bits at a time till the whole message is processed (every hash function I can think of works like this) has to have a padding scheme, so that when someone tries to hash some message that's not a multiple of r bits long, the message gets padded out to r bits. The only security relevance of the padding scheme is that it has to be invertible--given the padded string, there must always be exactly one input string that could have led to that padded string. If it isn't invertible, then the padding scheme would introduce collisions. For example, if your padding scheme was append zeros until you get the message out to a multiple of r bits, I could get collisions on your hash function by taking some message that was not a multple of r bits, and appending one or more zeros to it. Just appending a single one bit, followed by as many zeros as are needed to get to a multiple of r bits makes a fine padding scheme, so long as the one bit is appended to *every* message, even those which start out a multiple of r bits long. The Keccak team proposed adding a few extra bits to their padding, to add support for tree hashing and to distinguish different fixed-length hash functions that used the same capacity internally. They really just need to argue that they haven't somehow broken the padding so that it is no longer invertible They're making this argument by pointing out that you could simply stick the fixed extra padding bits on the end of a message you processed with the original Keccak spec, and you would get the same result as what they are doing. So if there is any problem introduced by sticking those extra bits at the end of the message before doing the old padding scheme, an attacker could have caused that same problem on the original Keccak by just sticking those extra bits on the end of messages before processing them with Keccak. -- Jerry --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
[Cryptography] Iran and murder
Alongside Phillip's comments, I'll just point out that assassination of key people is a tactic that the US and Israel probably don't have any particular advantages in. It isn't in our interests to encourage a worldwide tacit acceptance of that stuff. I suspect a lot of the broad principles we have been pushing (assassinations and drone bombings can be done anywhere, cyber attacks against foreign countries are okay when you're not at war, spying on everyone everywhere is perfectly acceptable policy) are in the short-term interests of various powerful people and factions in the US, but are absolutely horrible ideas when you consider the long-term interests of the US. We are a big, rich, relatively free country with lots of government scientists and engineers (especially when you consider funding) and tons of our economy and our society moving online. We are more vulnerable to widespread acceptance of these bad principles than almost anyone, ultimately, But doing all these things has won larger budgets and temporary successes for specific people and agencies today, whereas the costs of all this will land on us all in the future. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Crypto Standards v.s. Engineering habits - Was: NIST about to weaken SHA3?
One thing that seems clear to me: When you talk about algorithm flexibility in a protocol or product, most people think you are talking about the ability to add algorithms. Really, you are talking more about the ability to *remove* algorithms. We still have stuff using MD5 and RC4 (and we'll probably have stuff using dual ec drbg years from now) because while our standards have lots of options and it's usually easy to add new ones, it's very hard to take any away. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Sha3 and selecting algorithms for speed
Most applications of crypto shouldn't care much about performance of the symmetric crypto, as that's never the thing that matters for slowing things down. But performance continues to matter in competitions and algorithm selection for at least three reasons: a. We can measure performance, whereas security is very hard to measure. There are a gazillion ways to measure performance, but each one gives you an actual set of numbers. Deciding whether JH or Grostl is more likely to fall to cryptanalytic attack in its lifetime is an exercise in reading lots of papers, extrapolating, and reading tea leaves. b. There are low-end environments where performance really does matter. Those often have rather different properties than other environments--for example, RAM or ROM (for program code and S-boxes) may be at a premium. c. There are environments where someone is doing a whole lot of symmetric crypto at once--managing the crypto for lots of different connections, say. In that case, your symmetric algorithm's speed may also have a practical impact. (Though it's still likely to be swamped by your public key algorithms.) --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
[Cryptography] Performance vs security
There are specific algorithms where you have a pretty clear-cut security/performance tradeoff. RSA and ECC both give you some choice of security level that has a big impact in terms of performance. AES and SHA2 and eventually SHA3 offer you some secuirty level choices, but the difference in performance between them is relatively unimportant in most applications. Probably the coolest thing about Keccak's capacity parameter is that it gives you an understandable performance/security tradeoff, but the difference in performance between c=256 and c=512 will probably not be noticable in 99% of applications. Then there are algorithms that give you higher performance at the cost of more fragility. The example I can think of here is GCM, which gives you a pretty fast authenticated encryption mode, but which really loses security in a hurry if you reuse an IV. It seems like these two kinds of security/performance tradeoffs belong in different categories, somehow. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Crypto Standards v.s. Engineering habits - Was: NIST about to weaken SHA3?
On Oct 4, 2013, at 10:10 AM, Phillip Hallam-Baker hal...@gmail.com wrote: ... Dobertin demonstrated a birthday attack on MD5 back in 1995 but it had no impact on the security of certificates issued using MD5 until the attack was dramatically improved and the second pre-image attack became feasible. Just a couple nitpicks: a. Dobbertin wasn't doing a birthday (brute force collision) attack, but rather a collision attack from a chosen IV. b. Preimages with MD5 still are not practical. What is practical is using the very efficient modern collision attacks to do a kind of herding attack, where you commit to one hash and later get some choice about which message gives that hash. ... Proofs are good for getting tenure. They produce papers that are very citable. There are certainly papers whose only practical importance is getting a smart cryptographer tenure somewhere, and many of those involve proofs. But there's also a lot of value in being able to look at a moderately complicated thing, like a hash function construction or a block cipher chaining mode, and show that the only way anything can go wrong with that construction is if some underlying cryptographic object has a flaw. Smart people have proposed chaining modes that could be broken even when used with a strong block cipher. You can hope that security proofs will keep us from doing that. Now, sometimes the proofs are wrong, and almost always, they involve a lot of simplification of reality (like most proofs aren't going to take low-entropy RNG outputs into account). But they still seem pretty valuable to me for real-world things. Among other things, they give you a completely different way of looking at the security of a real-world thing, with different people looking over the proof and trying to attack things. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Sha3
http://keccak.noekeon.org/yes_this_is_keccak.html --John___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On Oct 1, 2013, at 5:58 PM, Peter Fairbrother zenadsl6...@zen.co.uk wrote: AES, the latest-and-greatest block cipher, comes in two main forms - AES-128 and AES-256. AES-256 is supposed to have a brute force work factor of 2^256 - but we find that in fact it actually has a very similar work factor to that of AES-128, due to bad subkey scheduling. Thing is, that bad subkey scheduling was introduced by NIST ... after Rijndael, which won the open block cipher competition with what seems to be all-the-way good scheduling, was transformed into AES by NIST. What on Earth are you talking about? AES' key schedule wasn't designed by NIST. The only change NIST made to Rijndael was not including some of the alternative block sizes. You can go look up the old Rijndael specs online if you want to verify this. -- Peter Fairbrother --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] are ECDSA curves provably not cooked? (Re: RSA equivalent key length/strength)
On Oct 1, 2013, at 12:51 PM, Adam Back a...@cypherspace.org wrote:
[Discussing how NSA might have generated weak curves via trying many choices
till they hit a weak-curve class that only they knew how to solve.]
...
But the more interesting question I was referring to is a trapdoor weakness
with a weak proof of fairness (ie a fairness that looks like the one in FIPS
186-3/ECDSA where we dont know how much grinding if any went into the magic
seed values). For illustration though not applicable to ECDSA and probably
outright defective eg can they start with some large number of candidate G
values where G=xH (ie knowing the EC discrete log of some value H they pass
off as a random fairly chosen point) and then do a birthday collision
between the selection of G values and diffrent seed values to a PRNG to find
a G value that they have both a discrete log of wrt H and a PRNG seed.
Bearing in mind they may be willing to throw custom ASIC or FPGA
supercomputer hardware and $1bil budgt at the problem as a one off cost.
This general idea is a nice one. It's basically a way of using Merkle's
puzzles to build a private key into a cryptosystem. But I think in general,
you are going to have to do work equal to the security level of the thing
you're trying to backdoor. You have to break it once at its full security
level, and then you get to amortize that break forever. (Isn't there something
like this you can do for discrete logs in general, though?)
Consider Dual EC DRBG. You need a P, Q such that you know x that solves xP =
Q, over (say) P-224. So, you arbitrarily choose G = a generator for the group,
and a scalar z, and then compute for
j = 1 to 2^{112}:
T[j] = jz G
Now, you have 2^{112} values in a group of 2^{224} values, right? So with
about another 2^{113} work, you can hit one of those with two arbitrary seeds,
and you'll know the relationship between them.
But this takes a total of about 2^{113} work, so it's above the claimed secuity
level of P-224. I suspect this would be more useful for something at the 80
bit security level--a really resourceful attacker could probably do a 2^{80}
search.
Adam
--John
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Crypto Standards v.s. Engineering habits - Was: NIST about to weaken SHA3?
Has anyone tried to systematically look at what has led to previous crypto failures? That would inform us about where we need to be adding armor plate. My impression (this may be the availability heuristic at work) is that: a. Most attacks come from protocol or mode failures, not so much crypto primitive failures. That is, there's a reaction attack on the way CBC encryption and message padding play with your application, and it doesn't matter whether you're using AES or FEAL-8 for your block cipher. b. Overemphasis on performance (because it's measurable and security usually isn't) plays really badly with having stuff be impossible to get out of the field when it's in use. Think of RC4 and DES and MD5 as examples. c. The ways I can see to avoid problems with crypto primitives are: (1) Overdesign against cryptanalysis (have lots of rounds) (2) Overdesign in security parameters (support only high security levels, use bigger than required RSA keys, etc.) (3) Don't accept anything without a proof reducing the security of the whole thing down to something overdesigned in the sense of (1) or (2). --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] RSA equivalent key length/strength
On Oct 2, 2013, at 9:54 AM, Paul Crowley p...@ciphergoth.org wrote:
On 30 September 2013 23:35, John Kelsey crypto@gmail.com wrote:
If there is a weak curve class of greater than about 2^{80} that NSA knew
about 15 years ago and were sure nobody were ever going to find that weak
curve class and exploit it to break classified communications protected by
it, then they could have generated 2^{80} or so seeds to hit that weak curve
class.
If the NSA's attack involves generating some sort of collision between a
curve and something else over a 160-bit space, they wouldn't have to be
worried that someone else would find and attack that weak curve class with
less than 2^160 work.
I don't know enough about elliptic curves to have an intelligent opinion on
whether this is possible. Has anyone worked out a way to do this?
The big question is how much work would have had to be done. If you're talking
about a birthday collision on the curve parameters, is that a collision on a
160 bit value, or on a 224 or 256 or 384 or 512 bit value? I can believe NSA
doing a 2^{80} search 15 years ago, but I think it would have had to be a top
priority. There is no way they were doing 2^{112} searches 15 years ago, as
far as I can see.
--John___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NIST about to weaken SHA3?
On Oct 1, 2013, at 4:48 AM, ianG i...@iang.org wrote: ... This could be the uninformed opinion over unexpected changes. It could also be the truth. How then to differentiate? Do we need to adjust the competition process for a tweak phase? Let's whiteboard. Once The One is chosen, have a single round + conference where each of the final contestants propose their optimised version. They then vote on the choice. I like the general idea here, but I suspect a vote at the end of a conference isn't going to yield great results. I'd hate to see something the designers opposed get adopted because they were outvoted by (say) a larger team. (OK, we can imagine many ways to do this ... point being that if NIST are going to tweak the SHA3 then we need to create a way for them to do this, and have that tweaking be under the control of the submitters, not NIST itself. In order to maintain the faith of the result.) The Keccak designers proposed reducing the capacity. You can find public statements about this online, including in the slides on their website. Also, the capacity is a parameter defined in the standard to allow an easy to understand performance/security tradeoff. Setting c=256 gives an across the board security level of 128 bits, if you believe the underlying Keccak permutation is good. The actual technical question is whether an across the board 128 bit security level is sufficient for a hash function with a 256 bit output. This weakens the proposed SHA3-256 relative to SHA256 in preimage resistance, where SHA256 is expected to provide 256 bits of preimage resistance. If you think that 256 bit hash functions (which are normally used to achieve a 128 bit security level) should guarantee 256 bits of preimage resistance, then you should oppose the plan to reduce the capacity to 256 bits. If you think a 256 bit hash function should only promise 128 bits of security, except in specific applicaitons like keyed hashes where it has been analyzed specifically and shown to get more, then you should (at least on technical grounds) like the proposal to reduce the capacity to 256 bits for a 256-bit hash output. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] check-summed keys in secret ciphers?
GOST was specified with S boxes that could be different for different applications, and you could choose s boxes to make GOST quite weak. So that's one example. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] RSA equivalent key length/strength
Having read the mail you linked to, it doesn't say the curves weren't generated
according to the claimed procedure. Instead, it repeats Dan Bernstein's
comment that the seed looks random, and that this would have allowed NSA to
generate lots of curves till they found a bad one.
it looks to me like there is no new information here, and no evidence of
wrongdoing that I can see. If there is a weak curve class of greater than
about 2^{80} that NSA knew about 15 years ago and were sure nobody were ever
going to find that weak curve class and exploit it to break classified
communications protected by it, then they could have generated 2^{80} or so
seeds to hit that weak curve class.
What am I missing? Do you have evidence that the NIST curves are cooked?
Because the message I saw didn't provide anything like that.
--John
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
[Cryptography] Sha3
If you want to understand what's going on wrt SHA3, you might want to look at the nist website, where we have all the slide presentations we have been giving over the last six months detailing our plans. There is a lively discussion going on at the hash forum on the topic. This doesn't make as good a story as the new sha3 being some hell spawn cooked up in a basement at Fort Meade, but it does have the advantage that it has some connection to reality. You might also want to look at what the Keccak designers said about what the capacities should be, to us (they put their slides up) and later to various crypto conferences. Or not. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Gilmore response to NSA mathematician's make rules for NSA appeal
On Sep 25, 2013, at 2:52 AM, james hughes hugh...@mac.com wrote: Many, if not all, service providers can provide the government valuable information regarding their customers. This is not limited to internet service providers. It includes banks, health care providers, insurance companies, airline companies, hotels, local coffee shops, book sellers, etc. where providing a service results in personal information being exchanged. The US has no corner on the ability to get information from almost any type of service provider. This is the system that the entire world uses, and should not be our focus. There are many places where there is no way to provide the service without having access to the data, and probably storing it. For those places, we are stuck with legal and professional and business safeguards. You doctor should take notes when you see him, and can be compelled to give those notes up if he can access them to (for example) respond to a phone call asking to refill your medications. There are rather complicated mechanisms you can imagine to protect your privacy in this situation, but it's hard to imagine them working well in practice. For that situation, what we want is that the access to the information is transparent--the doctor can be compelled to give out information about his patients, but not without his knowledge, and ideally not without your knowledge. But there are a lot of services which do not require that the providers have or collect information about you. Cloud storage and email services don't need to have access to the plaintext data you are storing or sending with them. If they have that information, they are subject to being forced to share it with a government, or deciding to share it with someone for their own business reasons, or having a dishonest employee steal it. If they don't have that information because their service is designed so they don't have it, then they can't be forced to share it--whether with the FBI or the Bahraini government or with their biggest advertiser. No change of management or policy or law can make them change it. Right now, there is a lot of interest in finding ways to avoid NSA surveillance. In particular, Germans and Brazilians and Koreans would presumably rather not have their data made freely available to the US government under what appear to be no restrictions at all. If US companies would like to keep the business of Germans and Brazilians and Koreans, they probably need to work out a way to convincingly show that they will safeguard that data even from the US government. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Gilmore response to NSA mathematician's make rules for NSA appeal
On Sep 18, 2013, at 3:27 PM, Kent Borg kentb...@borg.org wrote: You foreigners actually have a really big vote here. All those US internet companies want your business, and as you get no protections, in the current scheme, not even lip-service, you should look for alternatives. As you do, this puts pressure on the US internet companies, and they have the economic clout to put pressure on Feinstein and Polosi and all the others. This does not go far enough. The US government is not the only one inclined to steal information which it can reach, either because the information goes over wires the government can listen in on, or because the companies handling the data can be compelled or convinced to hand it over. Right now, we're seeing leaks that confirm the serious efforts of one government to do this stuff, but it is absolutely silly to think the US is the only one doing it. The right way to address this is to eliminate the need to trust almost anyone with your data. If Google[1] has all your cleartext documents and emails, they can be compelled to turn them over, or they can decide to look at them for business reasons, or they can be infiltrated by employees or contractors who look at those emails and documents. You are trusting a lot of people, and trusting a company to possibly behave against its economic interests and legal obligations, to safeguard your privacy. If they have encrypted data only, you don't have to trust them. It needs to be in their business interest to convince you that they *can't* betray you in most ways. -kb --John [1] I'm not picking on Google in particular--any US company may be compelled to turn over data they have. I imagine the same is true of any German or Korean or Brazilian company, but I don't know the laws in those places. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] PRISM-Proofing and PRISM-Hardening
On Sep 19, 2013, at 5:21 PM, Phillip Hallam-Baker hal...@gmail.com wrote: Criminals circumvent the WebPKI rather than trying to defeat it. If they did start breaking the WebPKI then we can change it and do something different. If criminals circumvent the PKI to steal credit card numbers, this shows up as fraud and is noticed without any need for a Snowden. Eavesdropping doesn't show up in such an obvious way. But financial transactions are easier than protecting the privacy of political speech because it is only money that is at stake. The criminals are not interested in spending $X to steal $0.5X. We can do other stuff to raise the cost of attack if it turns out we need to do that. Also, criminals find it harder to spend a few million up front before they get the first payoff. Nor can they appeal to patriotism or compel compliance via the law. If we want this to be a global infrastructure we have 2.4 billion users to support. If we spend $0.01 per user on support, that is $24 million. It is likely to be a lot more than that per user. It has to pay for itself ultimately, at least as well as email does. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] The paranoid approach to crypto-plumbing
On Sep 17, 2013, at 11:41 AM, Perry E. Metzger pe...@piermont.com wrote: I confess I'm not sure what the current state of research is on MAC then Encrypt vs. Encrypt then MAC -- you may want to check on that. Encrypt then MAC has a couple of big advantages centering around the idea that you don't have to worry about reaction attacks, where I send you a possibly malformed ciphertext and your response (error message, acceptance, or even time differences in when you send an error message) tells me something about your secret internal state. Perry --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] The paranoid approach to crypto-plumbing
For hash functions, MACs, and signature schemes, simply concatenating hashes/MACs/signatures gives you at least the security of the stronger one. Joux multicollisions simply tell us that concatenating two or more hashes of the same size doesn't improve their resistance to brute force collsion search much. The only thing you have to be sure of there is that the MAC and signature functions aren't allowed access to each others' secret keys or internal random numbers. Otherwise, MAC#1 can always take the value of MAC#2's key. This is just message, signature 1, signature 2 where the signatures are over the message only. For encryption algorithms, superencryption works fine. You can first encrypt with AES-CBC, then encrypt with Twofish-CFB, then with CAST5 in CFB mode. Again, assuming you are not letting the algorithms know each others' internal state or keys, if any of these algorithms are resistant to chosen plaintext attacks, then the combination will be. This doesn't guarantee that the combination will be any stronger than the strongest of these, but it will be no weaker. (Biham and later Wagner had some clever attacks against some chaining modes using single-DES that showed that you wouldn't always get anything stronger than one of the ciphers, but if any of these layers is strong, then the whole encryption is strong. An alternative approach is to construct a single super-block-cipher, say AES*Twofish*SERPENT, and use it in a standard chaining mode. However, then you are still vulnerable to problems with your chaining mode--the CBC reaction attacks could still defeat a system that used AES*Twofish*SERPENT in CBC mode, but not AES-CBC followed by Twofish-CFB followed by SERPENT-CTR. For key-encryption or transport, I think it's a little more complicated. If I need six symmetric keys and want to use three public key methods (say ECDH, NTRU, RSA) to transport the key, I've got to figure out a way to get the benefit from all these key exchange mechanisms to all six symmetric keys, in a way that I'm sure will not leak any information about any of them. Normally we would use a KDF for this, but we don't want to trust any one crypto algorithm not to screw us over. I think we can get this if we assume that we can have multiple KDFs that have secrets from one another. That is, I compute KDF1( key1, combined key exchange input) XOR KDF2( key2, combined key exchange input) The reason the two KDFs need keys that are secret from each other is because otherwise, KDF1 could just duplicate KDF2 and we'd get an all-zero set of keys. If KDF2 is strong, then KDF1 can't generate an output string with any relationship to KDF2's string when it doesn't know all the input KDF2 is getting. I agree with Perry that this is probably padlocking a screen door. On the other hand, if we want to do it, we want to make sure we guard against as many bad things as possible. In particular, it would be easy to do this in such a way that we missed chaining mode/reaction type attacks. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] The paranoid approach to crypto-plumbing
Arggh! Of course, this superencryption wouldn't help against the CBC padding attacks, because the attacker would learn plaintext without bothering with the other layers of encryption. The only way to solve that is to preprocess the plaintext in some way that takes the attacker's power to induce a timing difference or error message away. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] real random numbers
On Sep 15, 2013, at 6:49 AM, Kent Borg kentb...@borg.org wrote: John Kelsey wrote: I think the big problem with (b) is in quantifying the entropy you get. Maybe don't. When Bruce Schneier last put his hand to designing an RNG he concluded that estimating entropy is doomed. I don't think he would object to some coarse order-of-magnitude confirmation that there is entropy coming in, but I think trying to meter entropy-in against entropy-out will either leave you starved or fooled. If you are using a strong cryptographic PRNG, you only really need to know the amount of entropy you've collected in two situations: a. When you want to instantiate the PRNG and start generating keys from it. b. When you want to reseed the PRNG and know you will get some benefit from doing so. But those are pretty critical things, especially (a). You need to know whether it is yet safe to generate your high-value keypair. For that, you don't need super precise entropy estimates, but you do need at least a good first cut entropy estimate--does this input string have 20 bits of entropy or 120 bits? My view is that all the song and dance in /dev/random with keeping track of the entropy in the pool as it flows in and out is not all that useful, but there's just no way around needing to estimate entropy to know if your PRNG is in a secure state or not. --John -kb ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Security is a total system problem (was Re: Perfection versus Forward Secrecy)
On Sep 13, 2013, at 3:23 PM, Perry E. Metzger pe...@piermont.com wrote: The problem these days is not that something like AES is not good enough for our purposes. The problem is that we too often build a reinforced steel door in a paper wall. Also, if AES being insufficiently strong is our problem, we have a whole bunch of solutions easily at hand. Superencrypt successively with, say, Serpent, Twofish, CAST, Salsa, and Keccak in duplex mode. This has a performance cost, but it is orders of magnitude less overhead than switching to manual key distribution of one-time pads. It's hard for me to think of a real world threat that is addressed better by a one-time pad than by something cheaper and less likely to get broken via human error or attacks on the key management mechanism. Perry E. Metzgerpe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] real random numbers
Your first two categories are talking about the distribution of entropy--we assume some unpredictability exists, and we want to quantify it in terms of bits of entropy per bit of output. That's a useful distinction to make, and as you said, if you can get even a little entropy per bit and know how much you're getting, you can get something very close to ideal random bits out. Your second two categories are talking about different kinds of sources--completely deterministic, or things that can have randomness but don't always. That leaves out sources that always have a particular amount of entropy (or at least are always expected to!). I'd say even the squish category can be useful in two ways: a. If you have sensible mechanisms for collecting entropy, they can't hurt and sometimes help. For example, if you sample an external clock, most of the time, the answer may be deterministic, but once in awhile, you may get some actual entropy, in the sense that the clock drift is sufficient that the sampled value could have one of two values, and an attacker can't know which. b. If you sample enough squishes, you may accumulate a lot of entropy. Some ring oscillator designs are built like this, hoping to occasionally sample the transition in value on one of the oscillators. The idea is that the rest of the behavior of the oscillators might possibly be predicted by an attacker, but what value gets read when you sample a value that's transitioning between a 0 and a 1 is really random, changed by thermal noise. I think the big problem with (b) is in quantifying the entropy you get. I also think that (b) describes a lot of what commonly gets collected by the OS and put into the entropy pool. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] People should turn on PFS in TLS (was Re: Fwd: NYTimes.com: N.S.A. Foils Much Internet Encryption)
On Sep 10, 2013, at 3:56 PM, Bill Stewart bill.stew...@pobox.com wrote:
One point which has been mentioned, but perhaps not emphasised enough - if
NSA have a secret backdoor into the main NIST ECC curves, then even if the
fact of the backdoor was exposed - the method is pretty well known - without
the secret constants no-one _else_ could break ECC.
So NSA could advocate the widespread use of ECC while still fulfilling their
mission of protecting US gubbmint communications from enemies foreign and
domestic. Just not from themselves.
I think this is completely wrong.
First, there aren't any secret constants to those curves, are there? The
complaint Dan Bermstein has about the NIST curves is that they (some of them)
were generated using a verifiably random method, but that the seeds looked
pretty random. The idea here, if I understand it correctly, is that if the
guys doing the generation knew of some property that made some of the choices
of curves weak, they could have tried a huge number of seeds till they happened
upon one that led to a weak curve. If they could afford to try N seeds and do
whatever examination of the curve was needed to check it for weakness, then the
weak property they were looking for couldn't have had a probability much lower
than about 1/N.
I think the curves were generated in 1999 (that's the date on the document I
could find), so we are probably talking about less than 2^{80} operations
total. Unlike the case with the Dual EC generator, where a backdoor could have
been installed with no risk that anyone else could discover it, in this case,
they would have to generate curves until one fell in some weak curve class that
they knew about, and they would have to hope nobody else ever discovered that
weak curve class, lest all the federal users of ECC get broken at once.
The situation you are describing works for dual ec drbg, but not for the NIST
curves, as best I understand things.
--John
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
[Cryptography] one time pads
Switching from AES to one-time pads to solve your practical cryptanalysis problems is silly. It replaces a tractable algorithm selection problem with a godawful key management problem, when key management is almost certainly the practical weakness in any broken system designed by non-idiots. --Jhn ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Random number generation influenced, HW RNG
On Sep 9, 2013, at 6:32 PM, Perry E. Metzger pe...@piermont.com wrote: First, David, thank you for participating in this discussion. To orient people, we're talking about whether Intel's on-chip hardware RNGs should allow programmers access to the raw HRNG output, both for validation purposes to make sure the whole system is working correctly, and if they would prefer to do their own whitening and stretching of the output. Giving raw access to the noise source outputs lets you test the source from the outside, and there is alot to be said for it. But I am not sure how much it helps against tampered chips. If I can tamper with the noise source in hardware to make it predictable, it seems like I should also be able to make it simulate the expected behavior. I expect this is more complicated than, say, breaking the noise source and the internal testing mechanisms so that the RNG outputs a predictable output stream, but I am not sure it is all that much more complicated. How expensive is a lightweight stream cipher keyed off the time and the CPU serial number or some such thing to generate pseudorandom bits? How much more to go from that to a simulation of the expectdd behavior, perhaps based on the same circutry used in the unhacked version to test the noise source outputs? --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] In the face of cooperative end-points, PFS doesn't help
Your cryptosystem should be designed with the assumption that an attacker will record all old ciphertexts and try to break it later. The whole point of encryption is to make that attack not scary. We can never rule out future attacks, or secret ones now. But we can move away from marginal key lengths and outdated, weak ciphers. Getting people to do that is like pulling teeth, which is why we're still using RC4, and 1024-bit RSA keys and DH primes. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] XORing plaintext with ciphertext
It depends on the encryption scheme used. For a stream cipher (including AES in counter or OFB mode), this yields the keystream. If someone screws up and uses the same key and IV twice, you can use knowledge of the first plaintext to learn the second. For other AES chaining modes, it's less scary, though if someone reuses their key and IV, knowing plaintext xor ciphertext from the first time the key,iv pair was used can reveal some plaintext from the second time it was used. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Sep 7, 2013, at 3:25 PM, Christian Huitema huit...@huitema.net wrote: Another argument is “minimal dependency.” If you use public key, you depend on both the public key algorithm, to establish the key, and the symmetric key algorithm, to protect the session. If you just use symmetric key, you depend on only one algorithm. Of course, that means getting pair-wise shared secrets, and protecting them. Whether that’s harder or more fragile than maintaining a key ring is a matter of debate. It is probably more robust than relying on CA. Pairwise shared secrets are just about the only thing that scales worse than public key distribution by way of PGP key fingerprints on business cards. The equivalent of CAs in an all-symmetric world is KDCs. Instead of having the power to enable an active attack on you today, KDCs have the power to enable a passive attack on you forever. If we want secure crypto that can be used by everyone, with minimal trust, public key is the only way to do it. One pretty sensible thing to do is to remember keys established in previous sessions, and use those combined with the next session. For example, if we do Diffie-Hellman today and establish a shared key K, we should both store that key, and we should try to reuse it next time as an additional input into our KDF. That is, next time we use Diffie-Hellman to establish K1, then we get actual-key = KDF(K1, K, other protocol details). That means that if even one session was established securely, the communications are secure (up to the symmetric crypto strength) forevermore. - -- Christian Huitema --John___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG
There are basically two ways your RNG can be cooked: a. It generates predictable values. Any good cryptographic PRNG will do this if seeded by an attacker. Any crypto PRNG seeded with too little entropy can also do this. b. It leaks its internal state in its output in some encrypted way. Basically any cryptographic processing of the PRNG output is likely to clobber this. The only fix for (a) is to get enough entropy in your PRNG before generating outputs. I suspect Intel's RNG and most other hardware RNGs are extremely likely to be better than any other source of entropy you can get on your computer, but you don't have to trust them 100%. Instead, do whatever OS level collection you can, combine that with 256 bits from the Intel RNG, and throw in anything else likely to help--ethernet address, IP address, timestamp, anything you can get from the local network, etc. Hash that all and feed it into a strong cryptographic PRNG--something like CTR-DRBG or HMAC-DRBG from SP 800-90. If you do that, you will have guarded against both (a) and (b). --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Opening Discussion: Speculation on BULLRUN
Let's suppose I design a block cipher such that, with a randomly generated key and 10,000 known plaintexts, I can recover that key. For this to be useful in a world with relatively sophisticated cryptanalysts, I must have confidence that it is extremely hard to find my trapdoor, even when you can look closely at my cipher's design. At this point, what I have is a trapdoor one-way function. You generate a random key K and then compute E(K,i) for i = 1 to 1. The output of the one-way function is the ciphertext. The input is K. If nobody can break the cipher, then this is a one-way funciton. If only I, who designed it, can break it, then it's a trapdoor one-way function. At this point, I have a perfectly fine public key encryption system. To send me a message, choose a random K, use it to encrypt 1 through 1, and then send me the actual message encrypted after that in K. If nobody but me can break the system, then this cipher works as my public key. The assumption that matters here is that you know enough cryptanalysis that it would be hard to hide a practical attack from you. If you don't know about differential cryptanalysis, I can do the master key cryptosystem, but only until you learn about it, at which point you will break my cipher. But if you can, say, hide the only good linear characteristics for some cipher in its S-boxes in a way that is genuinely intractible for anyone else to find, then you have a public key cryptosystem. You can publish the algorithm for hiding new linear characteristics in an S-box--this becomes the keypair generation algorithm. The private key is the linear characteristic that lets you break the cipher with (say) 1 known plaintexts, the public key is the cipher definition. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware
On Sep 8, 2013, at 3:55 PM, Thor Lancelot Simon t...@rek.tjls.com wrote: ... I also wonder -- again, not entirely my own idea, my whiteboard partner can speak up for himself if he wants to -- about whether we're going to make ourselves better or worse off by rushing to the safety of PFS ciphersuites, which, with their reliance on DH, in the absence of good RNGs may make it *easier* for the adversary to recover our eventual symmetric-cipher keys, rather than harder! I don't think you can do anything useful in crypto without some good source of random bits. If there is a private key somewhere (say, used for signing, or the public DH key used alongside the ephemeral one), you can combine the hash of that private key into your PRNG state. The result is that if your entropy source is bad, you get security to someone who doesn't compromise your private key in the future, and if your entropy source is good, you get security even against someone who compromises your private key in the future (that is, you get perfect forward secrecy). Thor --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Opening Discussion: Speculation on BULLRUN
I don't see what problem would actually be solved by dropping public key crypto in favor of symmetric only designs. I mean, if the problem is that all public key systems are broken, then yeah, we will have to do something else. But if the problem is bad key generation or bad implementations, those will be with us even after we abandon all the public key stuff. And as Jon said, the trust problems get harder, not easier. With only symmetric crypto, whoever acts as the introducer between Alice and Bob can read their traffic passively and undetectably. With public key crypto, the introducer can do a man in the middle attack (an active attack) and risks detection, as Alice and Bob now have things signed by the introducer associating the wrong keys with Bob and Alice, respectively. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] FIPS, NIST and ITAR questions
Sent from my iPad On Sep 3, 2013, at 6:06 PM, Jerry Leichter leich...@lrw.com wrote: On Sep 3, 2013, at 3:16 PM, Faré fah...@gmail.com wrote: Can't you trivially transform a hash into a PRNG, a PRNG into a cypher, and vice versa? No. hash-PRNG: append blocks that are digest (seed ++ counter ++ seed) Let H(X) = SHA-512(X) || SHA-512(X) where '||' is concatenation. Assuming SHA-512 is a cryptographically secure hash H trivially is as well. (Nothing in the definition of a cryptographic hash function says anything about minimality.) But H(X) is clearly not useful for producing a PRNG. If you think this is obviously wrong, consider instead: H1(X) = SHA-512(X) || SHA-512(SHA-512(X)) Could you determine, just from black-box access to H1, that it's equally bad as a PRNG? (You could certainly do it with about 2^256 calls to H1 with distinct inputs - by then you have a .5 chance of a duplicated top half of the output, almost certainly with a distinct bottom half. But that's a pretty serious bit of testing) I don't actually know if there exists a construction of a PRNG from a cryptographically secure hash function. (You can build a MAC, but even that's not trivial; people tried all kinds of things that failed until the HMAC construction was proven correct.) -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] FIPS, NIST and ITAR questions
... Let H(X) = SHA-512(X) || SHA-512(X) where '||' is concatenation. Assuming SHA-512 is a cryptographically secure hash H trivially is as well. (Nothing in the definition of a cryptographic hash function says anything about minimality.) But H(X) is clearly not useful for producing a PRNG. You won't get a prf or stream cipher or prng or block cipher just out of collision resistance--you need some kind of pseudorandomness assumption. We expect general purpose hash functions like Keccak to provide that, but it doesn't follow from the collision resistance assumption, for exactly the reason you gave there--it's possible to design collision-resistant functions that leak input or are predictable in some bits. I don't actually know if there exists a construction of a PRNG from a cryptographically secure hash function. (You can build a MAC, but even that's not trivial; people tried all kinds of things that failed until the HMAC construction was proven correct.) The HMAC construction wouldn't give a PRF for your example of h(x) = sha512(x) || sha512(x) A single output would be trivial to distinguish from a 1024 bit random number. -- Jerry --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Opening Discussion: Speculation on BULLRUN
First, I don't think it has anything to do with Dual EC DRGB. Who uses it? My impression is that most of the encryption that fits what's in the article is TLS/SSL. That is what secures most encrypted content going online. The easy way to compromise that in a passive attack is to compromise servers' private keys, via cryptanalysis or compromise or bad key generation. For server side TLS using RSA, guessing just the client's random values ought to be enough to read the traffic. For active attacks, getting alternative certs issued for a given host and playing man in the middle would work. Where do the world's crypto random numbers come from? My guess is some version of the Windows crypto api and /dev/random or /dev/urandom account for most of them. What does most of the world's TLS? OpenSSL and a few other libraries, is my guess. But someone must have good data about this. My broader question is, how the hell did a sysadmin in Hawaii get hold of something that had to be super secret? He must have been stealing files from some very high ranking people. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Opening Discussion: Speculation on BULLRUN
On Thu, 5 Sep 2013 19:14:53 -0400 John Kelsey crypto@gmail.com
wrote:
First, I don't think it has anything to do with Dual EC DRGB. Who
uses it?
It did *seem* to match the particular part of the story about a
subverted standard that was complained about by Microsoft
researchers. I would not claim that it is the most important part of
the story.
One thing I can say for certain: NSA did not write SP 800-90. (That was the
implication of from the New York Times article.). That was mostly Elaine
Barker, my coworker, with me providing a lot of text around technical issues.
The algorithms all came out of work from ANSI X9.82 Part 3, which Elaine also
wrote with lots of input and text from me and the rest of the editing
committee. We worked with NSA people on this, and X9.82 Part 2 (the entropy
source section) was written entirely by NSA people, but it isn't easy for me to
see how anyone could stick a trapdoor in that. We're still working with NSA
people on SP 800-90B, which includes a lot of stuff on testing entropy sources.
When I started there was an RSA based algorithm which we eventually dropped
(analogous to bbs), Dual EC DRBG, the hash drbg (which is still in 800-90 in a
much-changed version for backward comatibility reasons, because the
standardization process took forever and people started designing to the X9.82
standard before it was done--this was also the reason we ended up keeping the
Dual EC DRBG) and an X9.17 based thing we got rid of. A bunch of the symmetric
stuff in there is mine--I made changes the the hash DRBG to address
time/memory/data tradeoffs, and wrote the HMAC DRBG and CTR DRBG. I also
changed around the hash df and wrote the bc df.
It is possible Dual EC DRBG had its P and Q values generated to insert a
trapdoor, though I don't think anyone really knows that (except the people who
generated it, but they probably can't prove anything to us at this point).
It's also immensely slower than the other DRBGs, and I have a hard time seeing
why anyone would use it. (But if you do, you should generate your own P and Q.)
...
Where do the world's crypto random numbers come from? My guess is
some version of the Windows crypto api and /dev/random
or /dev/urandom account for most of them.
I'm starting to think that I'd probably rather type in the results of
a few dozen die rolls every month in to my critical servers and let
AES or something similar in counter mode do the rest.
A d20 has a bit more than 4 bits of entropy. I can get 256 bits with
64 die rolls, or, if I have eight dice, 16 rolls of the group. If I
mistype when entering the info, no harm is caused. The generator can
be easily tested for correct behavior if it is simply a block cipher.
If you're trying to solve the problem of not trusting your entropy source, this
is reasonable, but it doesn't exactly scale to normal users. Entropy
collection in software is a pain in the ass, and my guess is that the
overwhelming majority of developers are happy to punt and just use the OS'
random numbers. That looks to be what happened with the Henninger and Lenstra
results regarding lots of RSA keys with shared moduli. That flaw implies a
huge number of easily factored RSA keys out there, thanks to insufficient
entropy and calling /dev/urandom on a system where it won't block even if it
thinks it has zero entropy. (This was a multi-level screw up, as I understand
it, between a Linux version and OpenSSL and the implementors of various
appliance network devices.).
It would be smarter for any crypto software to use the OS source for some seed
material, and then combine it with both unique or nearly unique information and
anything that's likely to have some entropy, and use that to initialize a good
PRNG. (I'd use CTR DRBG.) Your ethernet address doesn't have any entropy,
but it works like a salt in a password hashing scheme--an attacker must now
rerun his attack for each individual instance of the crypto software.
In general, software that uses crypto should probably be trying to gather
entropy wherever possible, not just trusting the OS. And it should use that
entropy plus the OS' entropy to seed its own PRNG. And it should throw in any
information that might distinguish this instance from other instances, to force
any attackers to rerun their attack on each instance individually.
When I saw the keystore stuff, I thought bad key generation. Henninger found
a bunch of RSA
keys from the same make of devices that were sharing primes, thanks to really
awful entropy collection. If those devices had been collecting 40 bits of
entropy for the first prime, she might never have found a pair of keys with a
shared prime. But someone using analogous methods might be able to generate
2^{40} primes ahead of time, and efficiently run each new RSA key sent in
against that list and break a large fraction of the keys.
I think long-term public keys
Re: [Cryptography] Backup is completely separate
The backup access problem isn't just a crypto problem, it's a social/legal problem. There ultimately needs to be some outside mechanism for using social or legal means to ensure that, say, my kids can get access to at least some of my encrypted files after I drop dead or land in the hospital in a coma. Or that I can somehow convince someone that it's really me and I'd like access to the safe deposit box whose password I forgot and lost my backup copy of. Or whatever. This is complicated by the certainty that if someone has the power to get access to my encrypted data, they will inevitably be forced to do so by courts or national security letters, and will also be subject to extralegal pressures or attacks to make them turn over some keys. I suspect the best that can be workably done now is to make any key escrow service's key accesses transparent and impossible to hide from the owner of the key, and then let users decide what should and shoudn't be escrowed. But this isn't all that great an answer. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
What I think we are worried about here are very widespread automated attacks,
and they're passive (data is collected and then attacks are run offline). All
that constrains what attacks make sense in this context. You need attacks that
you can run in a reasonable time, with minimal requirements on the amount of
plaintext or the specific values of plaintext. The perfect example of an
attack that works well here is a keysearch on DES; another example is the
attack on WEP.
All the attacks we know of on reduced-round AES and AES-like ciphers require a
lot of chosen plaintexts, or related key queries, or both. There is no way to
completely rule out some amazing new break of AES that makes the cipher fall
open and drop your plaintext in the attacker's lap, but I don't see anything at
all in the literature that supports that fear, and there are a *lot* of smart
people trying to find new ways to attack or use AES-like designs. So I put
this at the bottom of my list of likely problems.
Some attacks on public key systems also require huge numbers of encryptions or
specially formed ciphertexts that get sent to the target for decryption--we can
ignore those for this discussion. So we're looking at trying to factor an RSA
modulus or to examine a lot of RSA encryptions to a particular public key (and
maybe some signatures from that key) and try to get somewhere from that. I
don't know enough about the state of the art in factoring or attacking RSA to
have a strong intuition about how likely this is. I'm pretty skeptical,
though--the people. know who are experts in this stuff don't seem especially
worried. However, a huge breakthrough in factoring would make for workable
passive attacks of this kind, though it would have to be cheap enough to use to
break each user's public key separately.
Finally, we have the randomness sources used to generate RSA and AES keys.
This, like symmetric cryptanalysis, is an area I know really well. And my
intuition (backed by plenty of examples) is that this is probably the place
that is most likely to yield a practical offline attack of this kind. When
someone screws up the implementation of RSA or AES, they may at least notice
some interoperability problems. They will never notice this when they screw up
their implementation so that RNG only gets 32 bits of entropy before generating
the user's RSA keypair. And if I know that your RSA key is likely to have one
of these 2^{32} factors, I can make a passive attack work really well.
Comments?
--John
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
If I had to bet, I'd bet on bad rngs as the most likely source of a breakthrough in decrypting lots of encrypted traffic from different sources. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Functional specification for email client?
I think it makes sense to separate out the user-level view of what happens (the first five or six points) from how it's implemented (the last few points, and any other implementation discussions). In order for security to be usable, the user needs to know what he is being promised by the security mechanisms--not which digital signature scheme is being used or whether decoy messages are sent to frustrate traffic analysis. If something arrives in my inbox with a from address of nob...@nowhere.com, then I need to know that this means that's who it came from. If I mail something to nob...@nowhere.com, then I need to know that only the owner of that address will be able to read it. I need to know that nobody should be able to know with whom I'm communicating. But I don't need to know about keys, digital signatures, mix nets, etc. That's what I want to know as a cryptographer, but as a user, I just want to know what the security system is promising and how reliable its promises are. My intuition is that binding the security promises to email addresses instead of identities is the right way to proceed. I think this is something most people can understand, and more importantly it's something we can do with existing technology and no One True Name Authority In The Sky handing out certs. One side issue here is that this system's email address space needs to somehow coexist with the big wide internet's address space. It will really suck if someone else can get my gmail address n the secure system, but it will also be confusing if my inbox has a random assortment of secure and insecure emails, and I have to do some extra step to know which is which. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: Interesting bit of a quote
From: Travis H. [EMAIL PROTECTED] Sent: Jul 14, 2006 11:22 PM To: David Mercer [EMAIL PROTECTED] Cc: cryptography@metzdowd.com Subject: Re: Interesting bit of a quote ... The problem with this is determining if the media has been replaced. Absent other protections, one could simply write a new WORM media with falsified information. I can see two ways of dealing with this: 1) Some kind of physical authenticity, such as signing one's name on the media as they are produced (this assumes the signer is not corruptible), or applying a frangible difficult-to-duplicate seal of some kind (this assumes access controls on the seals). I think this is going to resolve to chain-of-custody rules of some kind. One problem is that so long as the company making the records is storing them onsite, it's hard for an outside auditor to be sure they aren't being tampered with. (Can the CEO really not work out a way to get one of his guys access to the tape storage vault?) 2) Some kind of hash chain covering the contents, combined with publication of the hashes somewhere where they cannot be altered (e.g. publish hash periodically in a classified ad in a newspaper). You could do the whole digital timestamping thing here. You could also just submit hashes of this week's backup tape to your auditor and the SEC or something. Another solution is to use cryptographic audit logs. Bruce Schneier and I did some work on this several years ago, using a MAC to authenticate the current record as it's written, and a one-way function to derive the next key. (This idea was apparently developed by at least two other people independently.) Jason Holt has extended this idea to use digital signatures, which makes them far more practical. One caveat is that cryptographic audit logs only work if the logging machine is honest when the logs are written. --John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Interesting bit of a quote
From: Anne Lynn Wheeler [EMAIL PROTECTED] Sent: Jul 11, 2006 6:45 PM Subject: Re: Interesting bit of a quote ... my slightly different perspective is that audits in the past have somewhat been looking for inconsistencies from independent sources. this worked in the days of paper books from multiple different corporate sources. my claim with the current reliance on IT technology ... that the audited information can be all generated from a single IT source ... invalidating any assumptions about audits being able to look for inconsistencies from independent sources. A reasonable intelligent hacker could make sure that all the information was consistent. It's interesting to me that this same kind of issue comes up in voting security, where computerized counting of hand-marked paper ballots (or punched cards) has been and is being replaced with much more user-friendly DREs, where paper poll books are being replaced with electronic ones, etc. It's easy to have all your procedures built around the idea that records X and Y come from independent sources, and then have technology undermine that assumption. The obvious example of this is rules for recounts and paper record retention which are applied to DREs; the procedures make lots of sense for paper ballots, but no sense at all for DREs. I wonder how many other areas of computer and more general security have this same kind of issue. --John Kelsey, NIST - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
A weird macro virus story
Guys, Some of my co-workers here at NIST got an email macro virus which appeared to be targeted to cryptographers. It appeared to be addressed to Moti Yung, and come from Lawrie Brown and Henri Gilbert (though that name was misspelled, maybe a transcription error from an alternate character set). Did any of you notice something like this? The email appeared to be addressed to several submission addresses for various crypto conferences. Wow, we've really made it as an influential group of people. We're important enough to be *targets* now --John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Cfrg] HMAC-MD5
From: [EMAIL PROTECTED] Sent: Mar 30, 2006 3:38 PM To: cryptography@metzdowd.com Subject: Re: [Cfrg] HMAC-MD5 I think that we have the evidence. The security MD5 depends heavily on a lot of nonlinearities in functions F,G,I and on carries in arithmetic additions. Nonlinearities in F,G,I are bitwise and very weak. Carries are much stronger, but the collision attacks showed that it is possible to controll them also. The question is, can these still be controlled when the attacker doesn't know the internal state of the chaining variables? If not, we may end up with second preimage attacks (which would finish off MD5 for most hashing applications!), but still not know how to attack HMAC. The attack model is really different! For what it's worth, though, I agree that we need to get rid of MD5 anywhere it's still in place, since the only thing we know about its security is that it's a lot less than anyone expected it to be even a year ago. In fact, we should have started this when Dobbertin had his free-start collision result. If we had, we'd be able to regard the devastating MD5 collisions we're seeing now in the same way we regard devastating attacks on FEAL. (If someone extends the best attack on FEAL to 64 rounds, that will be cool, but nobody will be scrambling to replace FEAL in their products and protocols.) Vlastimil Klima --John Kelsey, NIST - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
From: John Denker [EMAIL PROTECTED]
Sent: Mar 24, 2006 11:57 AM
To: Erik Zenner [EMAIL PROTECTED], cryptography@metzdowd.com
Subject: Re: Entropy Definition (was Re: passphrases with more than 160 bits
of entropy)
Erik Zenner wrote:
0 occurs with probability 1/2
each other number from 1 to 2^{160}+1 happens with
probability 2^{-161}.
Is anyone aware of whether (and where) this was
discussed in the literature, or what other approaches are taken?
This particular problem is contrived or at least exaggerated.
The example is a contrived, pathological case. And there are a bunch
of easy solutions once you know this is the distribution. The point
is to demonstrate that Shannon entropy gives you the wrong answer when
you try to use it here.
Now, you might ask if this is a problem in a real-world setting. So
let's imagine a very simple distribution--sequences of flips of a
biased coin. There are nice ways to remove the bias, but let's
imagine we're not doing that--instead, we're going to take a sequence
of coin flips, turn it into a 0/1 sequence, and then hash it down to
get a key.
Suppose the coin is biased so that heads comes up 0.9 of the time, and
that we generate 16-bit sequences at a time. The Shannon entropy of a
16-bit sequence is about 7.5, but the most likely symbol (all heads)
comes up about 18% of the time. So if we tried to generate a 7-bit
key, we'd lose on the attacker's first guess 18% of the time.
So, let's go further with this. We want to generate a DES key, with
56 bits of entropy. A 64-bit sequence produced with this biased coin
has Shannon entropy of about 60 bits, but an attacker has about a
1/1000 chance of guessing the DES key we derive from it on his first
try, which is unacceptable for just about any crypto application.
(The min-entropy is about ten bits.)
So yes, I used a contrived example to demonstrate the problem, but no,
the problem isn't just an ivory-tower concern.
The intuition here is that Shannon entropy is concerned with
communications channels, where we assume we have to send every
symbol. So when you have lots of low-probability symbols, and one of
those low-probability symbols is chosen 999 times out of a 1000, the
amount of bandwidth you need to transmit those symbols easily becomes
dominated by them. Most of the time, you're sending one of a large
set of symbols, and they all have to be distinguished from one
another.
The situation for the attacker is a lot more like having a channel
where it's acceptable to only send a small fraction of those symbols,
and just drop the rest. That is, it's okay for the attacker's model
to just ignore the huge set of low-probability symbols that occur
999/1000 of the time, and instead just transmit the highest
probability symbol 1/1000 of the time. Instead of transmitting it,
he's just guessing it. When he gets it right, he learns your DES
key.
...
This version serves to illustrate, in an exaggerated way, the necessity
of not assuming that the raw data words are IID (independent and identically
distributed).
Yes! The independent part is much harder to deal with than the
per-symbol distribution, in many real-world applications. The worst
of these are operating system events (used in Windows and various
Unixes to get random bits). Peter Gutmann did some really nice work
on this on a bunch of operating systems in a Usenix paper, and he
updated that and has a version of it on his website. If you're doing
OS-event sampling to generate random bits, you really ought to look at
his stuff. (But if you can get some hardware support, either directly
or via sampling the microphone like the Turbid design does, you're
probably on much firmer ground.)
--John Kelsey, NIST
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
From: Erik Zenner [EMAIL PROTECTED]
Sent: Mar 24, 2006 4:14 AM
To: cryptography@metzdowd.com
Subject: RE: Entropy Definition (was Re: passphrases with more than 160 bits
of entropy)
...
[I wrote:]
0 occurs with probability 1/2
each other number from 1 to 2^{160}+1 happens with
probability 2^{-161}.
The Shannon entropy on this distribution is 81.5 bits. But
if you tried to sample it once to generate an 80-bit Skipjack
key, half the time, I'd guess your key on my first try.
It's entirely correct that entropy is the wrong measure here, but
the question is how a good measure would look like.
There are a bunch of different entropy measures. Shannon entropy is
the right one for compression ratios and channel capacity, but not for
difficulty of guessing the string.
Assume that you have a sample space with N elements and an intelligent
attacker (i.e., one that tries the most probable elements first). Then
what you actually are interested in is that the attacker's probability
of success after q sampling attempts is as close as possible to the
lowest possible, namely q * 2^{-N}. A natural way of measuring this
seems to be some kind of distance between Pr[succ after q samples] and
the ideal function q * 2^{-N}. Such a measure might allow a designer
to decide whether a non-perfect distribution is still acceptable or
simply far out. Is anyone aware of whether (and where) this was
discussed in the literature, or what other approaches are taken?
The best discussion I've seen of this is in a couple papers by John
Pliam, about something he calls the work function, W(n). This is just
the probability of having guessed some secret value after n operations
(typically n guesses). You can generalize this to the number of
operations you have to carry out to have a given probability of
violating any security property (repeating a nonce, getting a block
collision in a block cipher chaining mode, etc). It's a very general
way of thinking about limiting parameters of crypto algorithms.
You're basically heading toward this idea in what you said above.
Let's think of this for an ideal case: a 128-bit key. When you have
done 2^k guesses of the key, you have a 2^{n-k} chance of having
guessed the key correctly. So if you graphed the work vs probability
of success on a log/log chart, you'd get a straight line for the ideal
case. W(n) = 2^{-128} n, as you said above.
Now, consider the case where you are generating a 128-bit key from a
bunch of sampled events on your computer that have been concatenated
together in a string S. Imagine making a list of all the possible
values of that string, and sorting them in descending order of
probability. You now have the best possible sequence of guesses.
W(n) is the sum of the first n probabilities.
If W(n) 2^{-128} n for any n, then the attacker has some point where
it is to his advantage to guess S instead of guessing your key.
So, this is where min-entropy comes in. Min-entropy is just
-lg(P[max]), the base 2 log of the maximum probability in the
distribution. You can convince yourself than if the min-entropy of S
is at least 128, then it's never easier to guess S than to guess K.
This is because each possible input string must have probability lower
than 2^{-128}, so the sum of the first n, W(n) n 2^{-128}.
This doesn't solve the much harder engineering/data analysis problem
of getting some reasonable approximation for the probabilities of S,
unfortunately. The easy way to solve that is to design a hardware RNG
in such a way that you pretty-much know the probabilty model to use
and can work out how to sample it to get a good estimate of the
probabilities. However, it is kind of nice to recognize that you only
have to estimate the largest probability to compute the min-entropy.
(It ought to be the easiest probability to measure and bound!)
Erik
--
Dr. Erik Zenner Phone: +45 39 17 96 06Cryptico A/S
Chief Cryptographer Mobile: +45 60 77 95 41Fruebjergvej 3
[EMAIL PROTECTED] www.cryptico.com DK 2100 Copenhagen
--John Kelsey, NIST
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
From: Jack Lloyd [EMAIL PROTECTED]
Sent: Mar 22, 2006 11:30 PM
To: cryptography@metzdowd.com
Subject: Re: Entropy Definition (was Re: passphrases with more than 160 bits
of entropy)
...
As an aside, this whole discussion is confused by the fact that there
are a bunch of different domains in which entropy is defined. The
algorithmic information theory sense of entropy (how long is the
shortest program that produces this sequence?) is miles away from the
information theory sense of entropy, and even that has a bunch of
different flavors.
For the information theory meanings of entropy, what you're really
talking about is a property of a probability distribution. You can do
that in terms of Shannon entropy if you want to know about bounds on
average bandwidth requirements for transmitting symbols from that
distribution. You can look at guessing entropy if you want to know
the -lg(expected work to guess the next symbol). You can look at
min-entropy if you want a hard bound on how many symbols you need to
sample to derive a 128-bit key that won't ever expose you to
weaknesses based on how you selected it. And so on.
Shannon entropy is the one most people know, but it's all wrong for
deciding how many samples you need to derive a key. The kind of
classic illustration of this is the probability distirbution:
0 occurs with probability 1/2
each other number from 1 to 2^{160}+1 happens with probability
2^{-161}.
The Shannon entropy on this distribution is 81.5 bits. But if you
tried to sample it once to generate an 80-bit Skipjack key, half the
time, I'd guess your key on my first try.
...
Yes. Let's say the contents of tommorrow's NY Times has n bits of entropy (we
probably can't actually calculate n, but we know it is a finite and fixed
value). And the LA Times from the same day will also have some amount of
entropy (call it n'). However, the entropy of the two papers combined would
(probably) not be n+n', but some number x st min(n,n') = x = n+n', because
the two papers will report on many of the same issues, carry some of the same
AP stories, and so forth. This redundant information doesn't increase the
entropy (reading the same AP story in a second newspaper wouldn't give you any
new information).
Right. If the probabilities are independent, you can add the
entropies. That's why they're defined in log terms.
--John
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
From: John Denker [EMAIL PROTECTED]
Sent: Mar 23, 2006 1:44 PM
To: John Kelsey [EMAIL PROTECTED], cryptography@metzdowd.com
Subject: Re: Entropy Definition (was Re: passphrases with more than 160 bits
of entropy)
...
With some slight fiddling to get the normalization right, 1/2
raised to the power of (program length) defines a probability
measure. This may not be the probability you want, but it
is a probability, and you can plug it into the entropy definition.
No, this isn't right for the algorithmic information theory meaning at
all. For that measure, we can intelligently discuss the entropy of a
specific random string, without reference to a probability model.
Indeed, what's the probability distribution of the sequence of bits
defined by Chaitin's Omega?
You can certainly complain that they should have used a different term
than entropy here, but you're not going to get these to be the same.
The problem is almost never understanding the definition of
entropy. The problem is almost always ascertaining what is
the correct probability measure applicable to the problem
at hand.
Well, you need to decide which of the probability distribution kinds
of entropy measures to use, and that differs in different
applications. If you use min-entropy or guessing entropy to estimate
the limits on how well some sequence of symbols will compress, you'll
get a pretty lousy answer. The same goes for using Shannon entropy to
determine whether you have collected enough entropy in your pool to
generate a 128-bit AES key.
...
0 occurs with probability 1/2
each other number from 1 to 2^{160}+1 happens with probability
2^{-161}.
The Shannon entropy on this distribution is 81.5 bits.
I think it is very close to 81 bits, not 81.5, but that is a minor
point that doesn't change the conclusion:
But if you
tried to sample it once to generate an 80-bit Skipjack key, half the
time, I'd guess your key on my first try.
Yeah, but if I sample it N times, with high probability I can generate
a large number of very good keys. This problem is faced by (and solved
by) any decent TRNG.
Hmmm. I've seen plenty of people get this wrong. If you use Shannon
entropy as your measure, and then say when I have collected 128 bits
of Shannon entropy in my pool, I can generate a 128-bit AES key, you
will generate keys that aren't as secure as you think they are. Now,
most TRNGs seem to evade this and many other problems by designing the
hardware to give a relatively simple probability model. If your
probability model is close to uniform, then all these probability
distribution based entropy measurements converge (with a constant
difference).
In the case above, we had better specify N. If you sample it 16
times, then you have a 2^{-16} chance of still being in a weak state.
Once you get enough samples that the probability of being in the
pathological worst case is negligible (whatever that means in your
application), then you can start generating output bits. That's
probably somewhere between N=32 and N=64.
--John
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Linux RNG paper
From: David Malone [EMAIL PROTECTED]
Sent: Mar 23, 2006 3:43 PM
To: Travis H. [EMAIL PROTECTED]
Cc: Heyman, Michael [EMAIL PROTECTED], cryptography@metzdowd.com, [EMAIL
PROTECTED], [EMAIL PROTECTED]
Subject: Re: Linux RNG paper
...
One metric might be guessability (mean number of guesses required
or moments there of). As you point out, Arikan and Massey have
shown that Shannon entropy are not particularly good estimates of
guessability. Generalisations of entropy, like Reni entropy do seem
to have meaning. The min-entropy mentioned in RFC 4086 seems
reasonable, though I don't think the rational given in the RFC is
actually correct.
Starting clarification:
Min-entropy of a probability distribution is
-lg ( P[max] ),
minus the base-two log of the maximum probability.
The nice thing about min-entropy in the PRNG world is that it leads to
a really clean relationship between how many bits of entropy we need
to seed the PRNG, and how many bits of security (in terms of
resistance to brute force guessing attack) we can get.
Suppose I have a string S with 128 bits of min-entropy. That means
that the highest probablity guess of S has probability 2^{-128}. I
somehow hash S to derive a 128-bit key. The question to ask is, could
you guess S more cheaply than you guess the key? When the min-entropy
is 128, it can't be any cheaper to guess S than to guess the key.
That's true whether we're making one guess, two guesses, ten guesses,
or 2^{127} guesses.
To see why this is so, consider the best case for an attacker: S is a
128-bit uniform random string. Now, all possible values have the same
probability, and guessing S is exactly the same problem as guessing
the key. (I'm ignoring any bad things that happen when we hash down
to a key, but those can be important to think about in a different
context.)
Now, why is this the best case for an attacker? Because it gives the
highest probability of guessing right on the nth guess. If the
min-entropy is 128, then the highest probability symbol must have
prob. 2^{-128}. If the next highest probability symbol has lower than
2^{-128} probability, then his second guess has lower probability.
And then the next highest probability symbol is constrained in the
same way.
This makes it really easy, once you're working in min-entropy terms,
to answer questions like do I have enough entropy in this string to
initialize a PRNG based on running AES-128 in counter mode?
David.
--John Kelsey, NIST
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: pipad, was Re: bounded storage model - why is R organized as 2-d array?
From: [EMAIL PROTECTED] Sent: Mar 21, 2006 9:58 AM To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED], cryptography@metzdowd.com Subject: Re: pipad, was Re: bounded storage model - why is R organized as 2-d array? ... | Anyone see a reason why the digits of Pi wouldn't form an excellent | public large (infinite, actually) string of random bits? The issue would be: Are there any dependencies amoung the bits of pi that would make it easier to predict where an XOR of n streams of bits taken from different positions actually come from - or, more weakly, to predict subsequent bits. When you build this scheme, you have to compare it to all other ways of generating random-looking keystream for a stream cipher. That means comparing it with generators which are guaranteed to be as hard to predict output bits for as a large integer is hard to factor, for example. Beyond the coolness factor of pi, it's hard to work out what additional guarantee we're getting from using it here. I don't know what the performance of the algorithm for generating the next n bits of pi looks like, but I'm guessing that I can do a fair number of AES/Serpent/Twofish/MARS/RC6/Blowfish/CAST/3DES/IDEA/RC5 calculations for the same cost. And we know how to build a stream cipher out of all those ciphers (running in OFB or counter mode) which is guaranteed to be as strong as the strongest of them. It's all about tradeoffs between performance, security, and what strong statements you can make about your security when you're done. In some applications, I am willing to give up a lot of performance for a solid proof of security; in others, I am willing to give up any hope of a proof of security to get really good performance. -- Jerry --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: NPR : E-Mail Encryption Rare in Everyday Use
From: Peter Saint-Andre [EMAIL PROTECTED] Sent: Feb 24, 2006 3:18 PM Subject: Re: NPR : E-Mail Encryption Rare in Everyday Use ... We could just as well say that encryption of remote server sessions is rare in everyday use. It's just that only geeks even do remote server sessions, so they use SSH instead of telnet. The thing is that email is in wide use (unlike remote server sessions). Personally I doubt that anything other than a small percentage of email will ever be signed, let alone encrypted (heck, most people on this list don't even sign their mail). I'm certain that only a small percentage of e-mail will ever be signed, so long as the tools to do that are so hard to use, and the value added so small. I find it useful to use encryption all the time on my private data, but virtually never use it for communications, because even among cryptographers the setup hassles are too great, and the value added too small. What we ultimately need is encryption and authentication that are: a. Automatic and transparent. b. Add some value or are bundled with something that does. c. Don't try to tie into the whole horrible set of PKI standards in terms of uniquely identifying each human and bit in the universe, and getting them to sign legally binding messages whose full interpretation requires reading and understanding a 30-page CPS. If email encryption became as transparent as SSL, most e-mail would be encrypted. This would still leave various phishing issues, etc., but eavesdropping and a lot of impersonation and spam and phishing would get much harder. Peter --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: thoughts on one time pads
bits biased 60/40 for your 128-bit AES key, you'll drop to 90+ bits of security; if you do that for your OTP, you'll reveal quite a bit of the normal ASCII text you send, because there's not very much entropy per bit.). The issue of preventing reuse is enormous. 3) How should one combine OTP with another conventional encryption method, so that if the pad is copied, we still have conventional cipher protection? In this manner, one could use the same system for different use cases; one could, for example, mail the pad, or leave it with a third party for the recipient to pick up, and you opportunistically theoretical security if the opponent doesn't get it, and you get empirical (conventional) security if they do. If you dig around, Rivest wrote a paper at Crypto 82 or 83 about randomizing encryption which is still pretty nice. To a first approximation, superencryption (encrypting the OTP-encrypted text with AES-CBC or some such thing) is always okay. 4) For authentication, it is simple to get excellent results from an OTP. You simply send n bytes of the OTP, which an attacker has a 2^-8n chance in guessing. How do we ensure message integrity? Is it enough to include a checksum that is encrypted with the pad? There are provably secure authentication schemes that use much less key material per message. Google for universal hashing and IBC Hash, and for provably secure authentication schemes. I seem to recall that Stinson has a really nice survey of this either webbed or in his book. (Anyone else remember?) Does it depend on our method of encipherment? Assuming the encipherment is XOR, is a CRC sufficient, or can one flip bits in the message and CRC field so as to cancel each other? Yep, you can flip bits, so long as you know the CRC polynomial. If the CRC polynomial is randomly chosen for each message, and used correctly, you get one of those provably-secure authentication schemes. If so, how should we compute a MIC? Just SHA-1, and include that right after the plaintext (that is, we encrypt the MIC so as to not reveal a preimage if SHA-1 is found to be invertible)? Read The Friendly Literature. ... The generation of random numbers is too important to be left to chance. -- Robert R. Coveyou -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Encryption using password-derived keys
From: Jack Lloyd [EMAIL PROTECTED]
Sent: Nov 29, 2005 11:08 AM
To: cryptography@metzdowd.com
Subject: Encryption using password-derived keys
The basic scenario I'm looking at is encrypting some data using a
password-derived key (using PBKDF2 with sane salt sizes and iteration
counts). I am not sure if what I'm doing is sound practice or just
pointless overengineering and wanted to get a sanity check.
My inclination is to use the PBKDF2 output as a key encryption key,
rather than using it to directly key the cipher (with the key used
for the cipher itself being created by a good PRNG). For some reason
the idea of using it directly makes me nervous, but not in a way I
can articulate, leading me to suspect I'm worried over nothing.
I think this is sensible for convenience reasons:
a. You can now change passwords without decrypting and re-encrypting
all your data. And similarly, if you ever had a reason to change
keys, you could do that without changing passwords.
b. You can now check the correctness of the entered password when you
decrypt the data encryption key (using authenticated encryption!),
rather than needing to process the whole data. (You could also just
generate a few extra check bits from PBKDF2.)
So, assuming using it as a KEK makes sense: At first I thought to use
XOR to combine the two keys, but realized that could lead to related
key attacks (by just flipping bits in the field containing the
encrypted key). That is probably not a problem with good algorithms,
but, then again, why take the chance; so I was thinking instead using
NIST's AES-wrap (or perhaps a less weirdly designed variant of it
that uses HMAC for integrity checking and AES in CBC mode for
confidentiality).
You almost certainly need to do encryption and authentication both on
your bulk data and your encrypted key. So why not do some mode that
does both (CCM being the obvious choice) for both the key encryption
and the bulk data encryption?
Like:
salt = PRNG_output(128)
iteration_count = 100
nonce = current nonce
DEK = PRNG_output(128)
KEK = PBKDF2(password,salt,iteration_count,128)
KeyBlob = CCM(KEK,0,DEK)
BulkData = CCM(DEK,nonce,plaintext)
Am I thinking about this far harder than I should?
I'll toss two other random ideas out there to see if they're useful to
you:
a. You may be worried about having a properly seeded PRNG available
to do your data encryption key generation. I think a sensible way
around this is to use both a PRNG output and some extra bits from
PBKDF2 to derive the first data encryption key. Like you could do:
X = PBKDF2(password,salt,iteration_count,256)
KEK = left 128 bits of X
S = right 128 bits of X
DEK = S xor PRNG_output(128)
b. You can use a clever trick by Abadi, Lomas and Needham to save
yourself most of the work you do on iterating the password hash during
the creation of the KEK, but not when rederiving it. Basically, what
you do is instead of setting an iteration count of 2^{21}, you
generate a big random salt, and omit 20 bits of it from the salt
that's stored with the encrypted file. This forces anyone trying to
re-derive the KEK to do about 2^{20} work on average, but it makes
generating the original encrypted file almost free. I'm always
surprised that this isn't used more often, because it's such a clever
trick.
-Jack
--John Kelsey
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: timing attack countermeasures (nonrandom but unpredictable delays)
From: Travis H. [EMAIL PROTECTED] Sent: Nov 16, 2005 11:37 PM To: David Wagner [EMAIL PROTECTED] Cc: cryptography@metzdowd.com Subject: Re: timing attack countermeasures (nonrandom but unpredictable delays) ... I don't follow; averaging allows one to remove random variables from the overall time, but you're still left with the real computation time plus the the deterministic delay I suggested as a function of the input. Specifically, time t(k,x) = f(k,x) + d(k,x) + r Where r is a random variable modelling all random factors, f is the time to compute the function, and d is the deterministic delay I suggested that is a function of the inputs. Averaging with repeated evaluations of the same k and x allows one to compute the mean value of r, and the sum f+d, but I don't see how that helps one seperate f from d. What am I missing? Let's assume d(k,x) is a random function of k||x, uniformly distributed between 0 and T where T is the average time of the encryption. I choose a set of inputs to the cipher x[0,1,2,...,n-1] so that if my guess of some part of k is right, I expect their total timing to be much lower than the average case. I get back Sum(f(k,x[i])+d(k,x[i])+r[i]). Suppose my guess is wrong. Now what we expect is: a. Sum(f(k,x[i]) = average value b. Sum(d(k,x[i]) = average value c. Sum(r[i]) = average value Suppose my guess is right. Now what we expect is: a. Sum(f(k,x[i]) = unusually low value b. Sum(d(k,x[i]) = average value c. Sum(r[i]) = average value So, right guesses still give me unusually low values, and wrong guesses still give me average-looking values. That means the timing channel is still there--d(k,x) only adds random noise. The only way to avoid this is to make d(k,x) somehow related to f(k,x). That's the idea behind things like having software or hardware go through both the 0 and 1 case for each bit processed in an exponent. In that case, we get d(k,x) being fast when f(k,x) is slow, and vice versa, and we close the timing channel. As long as d(k,x) is independent of f(k,x), I can still test guesses of parts of k or parts of x. --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: the effects of a spy
From: [EMAIL PROTECTED]
Sent: Nov 16, 2005 12:26 PM
Subject: Re: the effects of a spy
...
Remember Clipper? It had an NSA-designed 80-bit encryption
algorithm. One interesting fact about it was that it appeared to be
very aggressively designed. Most published algorithms will, for
example, use (say) 5 rounds beyond the point where differential
cryptoanalysis stops giving you an advantage. Clipper, on the other
hand, falls to differential cryptoanalysis if you use even one less
round than the specification calls for.
Nipick: The system was Clipper, the algorithm was Skipjack.
Why the NSA would design something so close to the edge has always
been a bit of a mystery (well, to me anyway). One interpretation is
that NSA simply has a deeper understanding than outsiders of where
the limits really are. What to us looks like aggressive design, to
them is reasonable and even conservative.
Three comments here:
a. Maybe they really do have a good generic differential-probability
limiting algorithm. There are algorithms like this in the public
world (they can be really computationally expensive, and they only
tell you upper bounds on a subset of possible attacks), and you'd
expect NSA to be interested, since they design a lot of algorithms.
It's not so intuitive to me that this would have applied to impossible
differentials unless they designed it to, though. In that case,
you're looking at differentials that can't appear instead of
differentials that appear too often.
b. Maybe they don't care that much about attacks that require some
huge number of plaintexts. The academic world has defined the game in
terms of total work being the critical parameter in the attack, and
we're seeing a push over time to move that to total attack cost.
(That is, it's not so interesting if you have a 2^{100} attack on a
128-bit block cipher, if the attack is impossible to parallelize.) If
someone publishes an attack on Twofish tomorrow which requires 2^{96}
plaintexts to break it faster than brute-force, we'll all agree that's
an attack. But there's no reason NSA has to think that way--maybe
they have some other parameter like 2^{n/2} texts for n-bit block
ciphers, after which they don't care about attacks because they're not
practical.
c. Maybe they just got it wrong. SHA0 and SHA1 demonstrate that this
is all too possible. (It's quite plausible to me that they have very
good tools for analyzing block ciphers, but that they aren't or
weren't sure how to best apply them to hash functions.)
...
Or maybe ... the reasoning Perry mentions above applies here. Any
time you field a system, there is a possibility that your opponents
will get hold of it. In the case of Clipper, where the algorithm was
intended to be published, there's no possibility about it. So why
make it any stronger than you have to?
Reducing Skipjack to 31 rounds wouldn't make a practical trapdoor
appear! You're still talking about 2^{34} chosen plaintexts!
-- Jerry
--John Kelsey
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On Digital Cash-like Payment Systems
From: cyphrpunk [EMAIL PROTECTED]
Sent: Oct 27, 2005 9:15 PM
To: James A. Donald [EMAIL PROTECTED]
Cc: cryptography@metzdowd.com, [EMAIL PROTECTED]
Subject: Re: On Digital Cash-like Payment Systems
On 10/26/05, James A. Donald [EMAIL PROTECTED] wrote:
How does one inflate a key?
Just make it bigger by adding redundancy and padding, before you
encrypt it and store it on your disk. That way the attacker who wants
to steal your keyring sees a 4 GB encrypted file which actually holds
about a kilobyte of meaningful data. Current trojans can steal files
and log passwords, but they're not smart enough to decrypt and
decompress before uploading. They'll take hours to snatch the keyfile
through the net, and maybe they'll get caught in the act.
Note that there are crypto schemes that use huge keys, and it's
possible to produce simple variants of existing schemes that use
multiple keys. That would mean that the whole 8GB string was
necessary to do whatever crypto thing you wanted to do. A simple
example is to redefine CBC-mode encryption as
C[i] = E_K(C[i-1] xor P[i] xor S[C[i-1] mod 2^{29}])
where S is the huge shared string, and we're using AES. Without
access to the shared string, you could neither encrypt nor decrypt.
CP
--John
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the orthogonality of anonymity to current market demand
From: R.A. Hettinga [EMAIL PROTECTED] Sent: Oct 25, 2005 8:34 AM To: cryptography@metzdowd.com, [EMAIL PROTECTED] Subject: On the orthogonality of anonymity to current market demand ... That is to say, your analysis conflicts with the whole trend towards T-0 trading, execution, clearing and settlement in the capital markets, and, frankly, with all payment in general as it gets increasingly granular and automated in nature. The faster you can trade or transact business with the surety that the asset in question is now irrevocably yours, the more trades and transactions you can do, which benefits not only the individual trader but markets as a whole. The prerequisite for all this is that when the asset changes hands, it's very nearly certain that this was the intention of the asset's previous owner. My point isn't to express my love for book-entry payment systems. There's plenty to hate about them. But if the alternative is an anonymous, irreversible payment system whose control lies in software running alongside three pieces of spyware on my Windows box, they probably still win for most people. Even bad payment systems are better than ones that let you have everything in your wallet stolen by a single attack. ... However anonymous irrevocability might offend one's senses and cause one to imagine the imminent heat-death of the financial universe (see Gibbon, below... :-)), I think that technology will instead step up to the challenge and become more secure as a result. What's with the heat-death nonsense? Physical bearer instruments imply stout locks and vaults and alarm systems and armed guards and all the rest, all the way down to infrastructure like police forces and armies (private or public) to avoid having the biggest gang end up owning all the gold. Electronic bearer instruments imply the same kinds of things, and the infrastructure for that isn't in place. It's like telling people to store their net worth in their homes, in gold. That can work, but you probably can't leave the cheapest lock sold at Home Depot on your front door and stick the gold coins in the same drawer where you used to keep your checkbook. And, since internet bearer transactions are, by their very design, more secure on public networks than book-entry transactions are in encrypted tunnels on private networks, they could even be said to be secure *in spite* of the fact that they're anonymous; that -- as it ever was in cryptography -- business can be transacted between two parties even though they don't know, or trust, each other. Why do you say internet bearer transactions are more secure? I can see more efficient, but why more secure? It looks to me like both kinds of payment system are susceptible to the same broad classes of attacks (bank misbehavior (for a short time), someone finding a software bug, someone breaking a crypto algorithm or protocol). What makes one more secure than the other? ... Cheers, RAH --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [fc-discuss] Financial Cryptography Update: On Digital Cash-like Payment Systems
From: cyphrpunk [EMAIL PROTECTED] Sent: Oct 24, 2005 5:58 PM To: John Kelsey [EMAIL PROTECTED] Subject: Re: [fc-discuss] Financial Cryptography Update: On Digital Cash-like Payment Systems ... Digital wallets will require real security in user PCs. Still I don't see why we don't already have this problem with online banking and similar financial services. Couldn't a virus today steal people's passwords and command their banks to transfer funds, just as easily as the fraud described above? To the extent that this is not happening, the threat against ecash may not happen either. Well, one difference is that those transactions can often be undone, if imperfectly at times. The whole set of transactions is logged in many different places, and if there's an attack, there's some reasonable hope of getting the money back. And that said, there have been reports of spyware stealing passwords for online banking systems, and of course, there are tons of phishing and pharming schemes to get the account passwords in a more straightforward way. The point is, if you're ripped off in this way, there's a reasonable chance you can get your money back, because the bank has a complete record of the transactions that were done. There's no chance of this happening when there's no record of the transaction anywhere. The payment system operators will surely be sued for this, because they're the only ones who will be reachable. They will go broke, and the users will be out their money, and nobody will be silly enough to make their mistake again. They might be sued but they won't necessarily go broke. It depends on how deep the pockets are suing them compared to their own, and most especially it depends on whether they win or lose the lawsuit. I don't think so. Suppose there's a widespread attack that steals money from tens of thousands of users of this payment technology. There seem to be two choices: a. The payment system somehow makes good on their losses. b. Everyone who isn't dead or insane pulls every dime left in that system out, knowing that they could be next. It's not even clear that these are mutually exclusive, but if (a) doesn't happen, (b) surely will. Nobody wants their money stolen, and I don't think many people are so confident of their computer security that they're willing to bet huge amounts of money on it. If you have to be that confident in your computer security to use the payment system, it's not going to have many clients. CP --John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: multiple keys to 1
From: rbg9000 [EMAIL PROTECTED] Sent: Sep 8, 2005 3:01 PM To: cryptography@metzdowd.com Subject: multiple keys to 1 Sorry, I really don't know much about encryption, and my google searches haven't turned up much. I wondering if it's possible to reduce a set of symmetric keys (aes, twofish, etc..) used to encrypt data into 1 key that can decrypt it? The straightforward symmetric crypto approach to this (it's not pretty or elegant, but it works) is to have each encrypting key be shared with the owner of the recipient key. Thus, we might have: Alice has key K_a Bob has key K_b Carol has key K_c Dave, the recipient, knows all three keys. Now, to encrypt a message to Dave, anyone can just do something like Encrypt(K_a,Message) Dave can try all possible keys, or can require that the sender prepend some kind of unique identifier, like Alice, Encrypt(K_a,Message) If you're looking for more elegant solutions, you end up needing to look at public key cryptosystems as Perry pointed out. Or look at multicast encryption and signature schemes, which have some neat stuff right at the boundary between symmetric and public key crypto. --John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Another entry in the internet security hall of shame....
Guys, Recently, Earthlink's webmail server certificate started showing up as expired. (It obviously expired a long time ago; I suspect someone must have screwed up in changing keys over or something, because the problem wasn't happening up until recently.) So, I contacted Earthlink's technical support, and I got this really encouraging reply / Dear John Kelsey, Thank you for contacting us. I understand that you are having problems viewing Webmail and that it send out an error on SSL certificate. I suggest that you try lowering the security settings of your Internet Explorer. Please follow the steps below on how to lower the security settings on your Internet Explorer. 1. Open Internet Explorer. 2. On the Task panel click on Internet Options. 3. Click on the Advance Tab. 4. Scroll down and uncheck [Warn about invalid site certificates]. 5. Remember to click on Apply. 6. Click on OK. You have successfully lower your Internet Explorer settings. Should you have any other concerns, please get back to us. You will receive a prompt reply. Sincerely, Therese B. 3613 EarthLink Electronic Customer Support EarthLink, Inc. Case ID 69080634 Looking for easy access to news, stocks, sports, and your favorite links? With the EarthLink Personal Start Page you can customize everything from the background colors to your local weather. For more information please visit http://start.earthlink.net Resolve your customer service questions on-line at our Account maintenance web site. To add email mailboxes, change passwords, or update your credit card information, go to: http://myaccount.earthlink.net You can also trade real-time messages with one of our friendly Live Chat representatives: http://support.earthlink.net/chat Or email us and get a response that day: http://support.earthlink.net/email Original Message Follows: - * Presented Article: 142454 * Name: John Kelsey * Email: [EMAIL PROTECTED] * Account Type: EarthLink Experience * Issue: Spam/Internet Fraud Problem * Detailed Issue: Report an Issue * Article Title: Protecting Yourself Against Email/Internet Fraud * Message Body: The SSL certificate for webmail.earthlink.net is expired. The webmail.atl.earthlink.net certificate is fine, it's just the webmail.earthlink.net certificate. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
herding attack paper submitted to ePrint archive
Guys, Yoshi and I have submitted a draft of the Herding Hash Functions paper up on the IACR ePrint server, and assuming there are no problems, it should be up reasonably soon. The core of the result is that when I can find lots of collisions for a hash function by brute force (or maybe analytically, though that gets more complicated), I can also break most systems that use a hash function to prove prior knowledge. I gave a rump session talk on this a few days ago at Crypto. --John Kelsey, NIST, August 2005 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: How much for a DoD X.509 certificate?
From: Peter Gutmann [EMAIL PROTECTED] Sent: Aug 11, 2005 7:42 AM To: cryptography@metzdowd.com Subject: How much for a DoD X.509 certificate? $25 and a bit of marijuana, apparently. See: http://www.wjla.com/news/stories/0305/210558.html http://www.wjla.com/news/stories/0105/200474.html Although the story doesn't mention this, the ID in question was the DoD Common Access Card, a smart card containing a DoD-issued certificate. To get a CAC, you normally have to provide two forms of verification... in this case I guess the two were photo ID of dead presidents and empirical proof that you know how to buy weed. Ah, so this was more of an attribute certificate, then. And that the certificate was issued based partly on a nonstandard proof of possession protocol. (More specifically, proof of possession with intent to distribute.) Peter. --John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Possible non-extension property for hash functions
From: Bill Frantz [EMAIL PROTECTED] Sent: Aug 6, 2005 6:27 PM To: cryptography@metzdowd.com Subject: Possible non-extension property for hash functions ... [Talking about the length-extension property.] H(x) = H(y) == H(x||s) = H(y||s) It seems to me that there might be a class of hash functions for which this property did not hold. While hashes in this class might require random access to the entire input, they could prevent the message extension class of attack exploited by Lucks and Daum (see http://th.informatik.uni-mannheim.de/people/lucks/HashCollisions) when they generated two Postscript files with very different output, but the same MD5 hash. There are actually a couple ways to do this. Either: a. Process the message sequentially, but do a final operation on the intermediate result before putting out an output hash, which introduces new collisions. Any truncated hash like SHA384 or SHA224 does this. As an added benefit, once you truncate enough bits (SHA384 truncates 128 bits), the length extension attack on prefix MAC goes away, and the Joux multicollisions and long message second preimage attacks Bruce and I came up with become much more difficult. (On the other hand, it doesn't seem easy to do any nice reduction proof from the strength of the SHA256 compression function to the strength of the SHA384 hash function.) b. Process the message multiple times, or give yourself random access, or whatever. Just processing through the message twice sequentially does eliminate the simple length-extension property, but there are variations on it that can still be used--that's why Joux multicollisions can be found even when you process the message twice sequentially. Are there other ways I'm not seeing to do this? ... Cheers - Bill --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: draft paper: Deploying a New Hash Algorithm
From: Steven M. Bellovin [EMAIL PROTECTED] Sent: Aug 5, 2005 12:04 PM To: Steve Furlong [EMAIL PROTECTED] Cc: cryptography@metzdowd.com .Subject: Re: draft paper: Deploying a New Hash Algorithm ... I'd have phrased it differently than Perry did. I'd say that the attackers are often cleverer *about security* than protocol designers, because insecurity is their specialty. Ordinary protocol desingers are good at designing those protocols, but they haven't been trained to think about security. Yes! I've noticed that it's really common for me to work on a project for a very short time (like an hour or two), and start noticing all kinds of security holes, including a lot of stuff with nothing to do with cryptography. I'll still be asking very basic questions of the other people on the project about how things are *supposed* to work, but be pointing out attacks they never thought of at the same time. I think this is just a different way of thinking. Attackers and security people do this all the time. Most normal people never do--it's like once they've got the rules in their heads, that's what's possible, and they don't even think about it. How many times, working on security for some system, have you pointed out an attack, only to hear some variation on but who would think of that? And you can see the same thing happening in discussions of homeland security and counterterrorism stuff. It's like most people look at the national guardsmen in the airport, and say whew, I feel safer, rather than what the heck are those guys supposed to do to stop hijacked planes crashing into buildings? I like your starting points, but I think the real approach to thinking about this is a bit broader. It has to do with understanding the rules, and trying to ask, for each one, and what makes me obey that rule? or what would happen if I didn't do such and so? --Steven M. Bellovin, http://www.cs.columbia.edu/~smb --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: solving the wrong problem
From: Perry E. Metzger [EMAIL PROTECTED] Sent: Aug 6, 2005 2:28 PM To: cryptography@metzdowd.com Subject: solving the wrong problem Frequently, scientists who know nothing about security come up with ingenious ways to solve non-existent problems. Take this, for example: http://www.sciam.com/article.cfm?chanID=sa003articleID=00049DB6-ED96-12E7-AD9683414B7F Basically, some clever folks have found a way to fingerprint the fiber pattern in a particular piece of paper so that they know they have a particular piece of paper on hand. It is claimed that this could help stop forged passports. Unfortunately, the invention is wholely useless for the stated purpose. A couple of these guys gave a talk at NIST recently. The thing is, I can think of a bunch of uses for the thing they're doing. This looks genuinely useful as a tool. Whether they've worked out how to use the tool to best effect is a different question. The passport idea doesn't add much, as you pointed out. The reason is that the thing you care about there is that the information on the passport hasn't been tampered with and originated from the right source. An identical copy of my passport is no worse than the original. On the other hand, think about the uses of this technology for paper bearer instruments. Design travelers' checks that include a 2D barcode with a BLS signature, bound to the piece of paper, and you can print the damned thing on regular paper if the readers are cheap enough. Similar things apply to stamps, tickets, etc. If you can get readers into peoples' homes, you can even allow home printing of tickets, travelers' checks, etc., each bound to a specific piece of paper. Add a reader to your favorite DVD player platform (I think it's the same basic hardware as is used in a DVD player), and you can uniquely sign content on a disc, and use the player's hardware to enforce only playing content when the disc's biometric matches the signed content. You could use the technique to scan small bits of flat surfaces of all your stuff (the basic technique works on paper, plastic, and metal, at least; I'm not sure if it works on wood or glass), record the biometrics and locations of the scans, and provide this to the police when your house gets burgled. There are some wonderful potential uses for this technology in making paper-based voting systems *much* more secure. And on and on. If I were in the business of producing tamper-resistant paper, I'd be scared to death. ... Anyway, I have a larger point. I read about such stuff every day -- wacky new ways of building tamper proof tokens, quantum cryptography, and other mechanisms invented by smart people who don't understand threat models at all. Yes. As I said, sometimes this stuff looks almost useless (like quantum cryptography), other times it looks like it may provide powerful tools, despite the fact that its designers don't know much about how to use those tools yet. The same is often true in cryptography, where we have some very theoretical work which sometimes ends up having enormous practical consequences. We already have the term snake oil for a very different type of bad security idea, and the term has proven valuable for quashing such things. We need a term for this sort of thing -- the steel tamper resistant lock added to the tissue paper door on the wrong vault entirely, at great expense, by a brilliant mind that does not understand the underlying threat model at all. In my consulting days, I used to use the term padlocking the screen door for the related phenomenon of piling security on one part of the system while ignoring the bigger vulnerabilities. But this is a bit different Perry --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Possibly new result on truncating hashes
Guys,
I have what seems like a new and interesting result, which I
haven't seen before, but which may or may not be new.
The high order bit is that you can't generally guarantee
that truncating your hash (chopping off some bits) won't
weaken it. That is, if you chop SHA256 off to 160 bits as a
replacement for SHA1 (something I'm working on with Niels
Ferguson for X9 right now), it's possible that there's no
attack on SHA256, but there is an attack on SHA160.
How could this work? Suppose we have an algorithm like the
Wang attacks on MD5, SHA0, or SHA1 for finding a single
collision pair. The algorithm returns a single collision
pair on the first 160 bits of SHA256 for (say) 2^{64} work.
(Remember that this is just an example--I don't have any
such algorithm!) Each time the algorithm is run, it gives a
new, unrelated collision pair, and the remaining 96 bits are
completely randomized by the collision pair.
Now, this is an attack on SHA256 truncated to 160 bits.
Does it lead to an attack on SHA256 as a whole? If it does,
then we can make a reduction proof that says that the
truncated hash is strong if the original hash is strong.
Unfortunately, we can't make this argument, because this
postulated collision algorithm can't be used to find a
collision in the whole SHA256 more efficiently than brute
force.
Let's do the counting argument: Each time we call the
160-bit collision algorithm, we get a new pair which has the
same first 160 bits of SHA256 output, and random unrelated
last 96 bits of SHA256 output. Each pair has a probability
of 2^{-96} of colliding in the remaining bits. So, to get a
collision on the whole SHA256 using this 160-bit collision
algorithm, we expect to have to try about 2^{96} collision
pairs, each found at a cost of 2^{64}. The resulting work
is 2^{64} * 2^{96} = 2^{160}, more than a straight
brute-force collision search on SHA256.
What does this mean? It means that just because you have a
good 256-bit hash, you can't necessarily make a good 160 bit
hash from it. You might be able to--it seems like you
usually will be able to--but there's no guarantee.
Comments? Is this some well-known result that I'm
rediscovering?
--John
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: ID theft -- so what?
From: Aram Perez [EMAIL PROTECTED] Sent: Jul 14, 2005 10:45 AM To: Cryptography cryptography@metzdowd.com Subject: Re: ID theft -- so what? RANT-PET_PEEVEWhy do cryptography folks equate PKI with certificates and CAs? One nontrivial reason is that many organizations have spent a lot of time and money building up elaborate rules for using PKI, after long negotiations between legal and technical people, many hours of writing and revising, gazillions of dollars in consultants' time, etc. So, anytime you start doing anything involving public key cryptography, all this machinery gets invoked, for bureaucratic reasons. That is, you've now trespassed on PKI turf, and you'll have to comply with this enormous set of rules. I know of a couple cases where this led to really irritating results. In one, a friend of mine was using a digital signature to verify some fairly trivial thing, but was told it was against policy to use a digital signature without the whole PKI. (I believe he changed the documentation, so that he was using a modular arithmetic checksum instead of a signature verification.) As a consultant, I designed and evaluated a lot of systems that used public key cryptography. None of the successful ones tried to use the whole X.509 + CRL + CPS + everything else overhead--typically, they just used a one-deep hierarchy, where the keypair was put into the device by the manufacturer along with a copy of the top-level public key used to sign all device public keys. This works, because it doesn't try to incorporate the output of 20 years of make-work programs in cryptography (they weren't intended that way, but that's largely how they turned out), and it doesn't try to incorporate every idea that might be useful anywhere in the world into some very limited and simple application. Aram Perez --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
halloween hash bash reminder--July 15 deadline
Guys, This is just a reminder that the NIST hash workshop (Oct 31-Nov 1 of this year) is still taking submitted talks, abstracts, etc., until July 15. There are no proceedings, so there should not be any problem publishing things that you discuss at this workshop. A major goal of doing this is to get people to discuss interesting ongoing work so we can understand it now, rather than after we've made decisions about how to react to all the excitement in the hash function world. (For what it's worth, I plan on presenting some new hash function results with Yoshi Kohno that we intend to publish somewhere else. I expect we'll post these on the ECRYPT server before that.) This workshop is going to have a big impact on decisions like whether we should do some AES-like process to get a new hash function standard, whether we should try to standardize on some additional algorithms (like Whirlpool or the Russian standard GOST hash function), etc. Taking part is a great opportunity to influence those decisions. If you have something new to say about hash functions, or something old that should be repeated, send us some slides, or at least an extended abstract, and we'll see whether we can fit you onto the agenda for some discussion time. --John Kelsey, NIST, July 2005 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: /dev/random is probably not
From: Charles M. Hannum [EMAIL PROTECTED] Sent: Jul 3, 2005 7:42 AM To: Don Davis [EMAIL PROTECTED] Cc: cryptography@metzdowd.com Subject: Re: /dev/random is probably not ... Also, I don't buy for a picosecond that you have to gather all timings in order to predict the output. As we know from countless other attacks, anything that gives you some bits will reduce the search space and therefore weaken the system, even if it does not directly give you the result. I think you're landing on the genuinely hard problem here. Designing a PRNG intelligently is an exercise in design and cryptanalysis, so long as you get to assume that you know how much entropy you're getting. But actually getting reliably entropy estimates is: a. A data analysis problem, where you never really get a final answer, you just get the best model you knew how to test and don't find strong evidence to discard it, and b. Enormously sensitive to implementation details that are hard to deal with in software. In a hardware RNG design, you can at least analyze test-mode raw outputs of the ring oscillator or whatever, build a statistical model, and know that the same basic model will also describe the devices in the field. They may vary because of manufacturing defects, changes in the field (like heating/cooling or component failure), etc., but you at least know what kind of thing you've got. With software sources, there's pretty much no limit to what changes the designer of the hardware is allowed to make to your devices, so long as he keeps the interface the same. You do lots of analysis on a machine with a spinning disk drive, and end up on one with one networked drive and one flash drive, or some such horrible thing. Additionally, building a probability model for stuff you observe on a general purpose computer is *hard*, because there's so much complicated deterministic stuff going on. Even if you're using the same machine and setup to collect entropy in production as you did to build your probability model for entropy estimation, it's hard to have enormous confidence in the correctness of your estimates. How much of that apparently random behavior you were getting when you sampled the cycle counter in a tight loop was because of genuine unpredictability, and how much was because of the very patterned but complicated stuff going on behind the scenes on your machine? --John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: NIST Public Workshop on Cryptographic Hashes
From: Perry E. Metzger [EMAIL PROTECTED] Sent: Jun 15, 2005 8:00 AM To: cryptography@metzdowd.com Subject: NIST Public Workshop on Cryptographic Hashes [Discussing the NIST public hash function workshop.] The workshop will be held on October 31 and November 1, 2005, from 9 a.m. to 5:30 p.m. Informally, we're calling this the halloween hash bash. Come dressed as your favorite hash function! If you want to have some impact on where we go with hash functions, this is a good thing to attend Perry E. Metzger [EMAIL PROTECTED] --John Kelsey, NIST - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: expanding a password into many keys
From: Greg Rose [EMAIL PROTECTED] Sent: Jun 14, 2005 2:54 PM To: EKR [EMAIL PROTECTED] Cc: Ian G [EMAIL PROTECTED], cryptography@metzdowd.com Subject: Re: expanding a password into many keys ... You know, the proof that HMAC is a good MAC requires that the *compression function* of the underlying hash is good. And for almost all applications like this one, both the input password and the sequence number, tag name, or whatever the second input is, all fit into a single compression function block. Actually, there are quite a few attacks on these schemes that amount to messing up that property--getting the message to span multiple blocks (as with the length extension attacks). The other thing that any direct use of a crypto primitive can't help with is sliding data between fields. If you don't encode your fields in some parseable way before feeding them into the hash/MAC/block cipher/whatever, you get these weird attacks where I either request key XXX with optional additional string Y, or I request key XX with optional additional string XY, and I get the same result. Usually this doesn't lead to a practical attack, but it puts an extra burden on the engineer using the KDF, since he or she had better understand this attack and make sure it doesn't apply. Adams, Kramer, Mister, and Zucherato have a recent paper pointing out a bunch of these problems with widely used KDFs. I think of these as analogous to the length-extension property of hash functions or the complementation property of DES--it doesn't keep the crypto mechanism from being used securely, but it does make the job of an engineer trying to use it needlessly more complicated. Greg RoseINTERNET: [EMAIL PROTECTED] --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Collisions for hash functions: how to exlain them to your boss
From: Eric Rescorla [EMAIL PROTECTED] Sent: Jun 14, 2005 9:36 AM Subject: Re: Collisions for hash functions: how to exlain them to your boss [Discussing the MD5 attacks and their practicality, especially the recent postscript demonstration.] ... But everything you've just said applies equally to my JavaScript example. It's not a security vulnerability in the browser or the data format that it displays differently depending on the context. It's an intentional feature! I think our disagreement here has to do with what we're seeing from the attack. You're seeing a specific attack vector--use conditional execution/display + the ability to find specific collisions of a particular form to yield these nice attacks where we have two messages that amount to X ||M0||M1 X*||M0||M1 where when the first part of the message is X, some kind of conditional execution displays M0, while X* leads to the display of M1. And I think you're right to say that in many cases, once you're viewing the result of blindly executing programs that I send you, you're vulnerable to other attacks that are about as damaging. Now, it's certainly possible imagine cases where this kind of conditional execution wouldn't be allowed to access anything outside the file, but once you've decided to put in a full featured scripting language, it's not that much of a stretch to think you'll let me read the system time. I'm seeing a more general pattern of attacks, in which X and X* amount to context for the display of whatever follows them. That seems to me to encompass a lot more than macros and script files with conditional execution. And even when I don't have a specific attack in mind, it worries me that if I'm trying to help someone safely use MD5, I've got to think through whether there is any way at all to make this kind of attack pattern work. It's a heck of a lot easier to say don't use MD5. ... -Ekr --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: expanding a password into many keys
From: Ian G [EMAIL PROTECTED] Sent: Jun 12, 2005 11:27 AM To: cryptography@metzdowd.com Subject: expanding a password into many keys I'd like to take a password and expand it into several keys. It seems like a fairly simple operation of hashing the concatonatonation of the password with each key name in turn to get each key. Are there any 'gotchas' with that? There's a length extension property with what you're doing, so if I get to choose your key names, I can do something unpleasant to you. Suppose I know the length of pass, and get to choose two key names, K1_name and K2_name. You give me K1 = sha1( pass||K1_name), then I need to guess K2_name. I can choose K2_name to be K1_name, appropriately padded to the full block size exactly as it will be in the SHA1 computation that produces K1. Then, I can compute K2 on my own, because the only effect of the secret value pass on K2 is going through K1. This doesn't look like an especially realistic attack model, but I'm not sure what you're doing with this iang --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Papers about Algorithm hiding ?
From: Ian G [EMAIL PROTECTED] Sent: Jun 7, 2005 7:43 AM To: John Kelsey [EMAIL PROTECTED] Cc: Steve Furlong [EMAIL PROTECTED], cryptography@metzdowd.com Subject: Re: Papers about Algorithm hiding ? [My comment was that better crypto would never have prevented the Choicepoint data leakage. --JMK] Sure it would. The reason they are not using the tools is because they are too hard to use. If the tools were so easy to use that it was harder to not use them, then they'd be used. Consider Citigroup posted today by Bob. They didn't encrypt the tapes because the tools don't work easily enough for them. So, this argument might make sense for some small business, but Citigroup uses a *lot* of advanced technology in lots of areas, right? I agree crypto programs could be made simpler, but this is really not rocket science. Here's my guess: encrypting the data would have required that someone make a policy decision that the data be encrypted, and would have required some coordination with the credit agency that was receiving the tapes. After that, there would have been some implementation costs, but not all *that* many costs. Someone has to think through key management for the tapes, and that's potentially a pain, but it's not intractible. Is this really more complicated than, say, maintaining security on their publically accessible servers, or on their internal network? ... The other way of looking at Choicepoint - change the incentives - is a disaster. It will make for a compliance trap. Compliance *may* protect the data or it may have completely the opposite effect, the situation with 'unintended consequences' in such a case is likely to be completely unpredictable. The only thing we can guarantee is that costs will go up. Well, Choicepoint is a bit different, right? I mean, as I understand it the big disclosure happened because they sold peoples' data to criminals, but they were in the business of selling peoples' data. They just intended to sell it only to people of good intention, as far as I can tell. (Perhaps they should have demanded X.509 certificates from the businesses buying the data and checked the evil bit.) I just can't see how cryptography could have helped prevent that attack, other than by making the data that Choicepoint depends on harder to get in the first place. It's much cheaper and much more secure to simply improve the tools. But this does no good whatsoever if there's not some reason for the people holding the data to use those tools. Everyone with a network presence and any kind of high profile does, in fact, use moderately complicated computer security tools like routers, firewalls, VPNs, virus scanners, and spyware detectors. Everyone has to deal with keeping their boxes up to date on patches. However imperfectly, it seems like Citigroup and Choicepoint and the rest can actually do those things. So when you excuse their failures to secure customer data with the tools aren't there, this sounds absolutely implausible to me. I'm not crazy about a HIPAA-style mandate for encryption and shredders either, but we have this basic problem: a. It's basically easy to buy or find some amount of data about many people. b. It's basically easy to use that amount of data to get credit in their name. I suspect a better solution than trying to regulate data brokers is to make it more expensive to give credit to Alice under Bob's name. The thing that imposes the cost on me isn't when someone finds my SSN, it's when someone takes out a bunch of loans which I'm then expected to pay back. Then it becomes my problem to resolve the disputes created by the lender's desire to extend credit at minimal cost. (The lender also loses money, of course. But much of the cost is shifted to the identity theft victim.) iang --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Papers about Algorithm hiding ?
From: Ian G [EMAIL PROTECTED] Sent: Jun 4, 2005 6:43 AM To: Steve Furlong [EMAIL PROTECTED] Cc: cryptography@metzdowd.com Subject: Re: Papers about Algorithm hiding ? GPG is an application that could be delivered by default in all free OSs. BSD is more or less installed automatically with SSH installed. Linux machines that are set up are also generally set up with SSH. I think you need one more step here to get the protective coloration effect you'd like, where encrypted files aren't automatic evidence of wrongdoing: During installation, generate 50 or so random passwords with too much entropy to feasibly guess (easy to do when no user need ever remember them), and encrypt some reasonable-length files full of binary zeros with them. The number of randomly-generated files needs to be randomized, naturally, and probably should follow some kind of distribution with a big tail to the right, so that it's not that uncommon for a random install to put several hundred encrypted files on the drive. The value of this is that an attacker now sees encrypted files on every machine, most of which nobody on Earth can decrypt. If this is normal, then it's not evidence. (There are probably a bunch of issues here with putting plausible tracks in the logs, datestamps on the files, etc. But it seems like something like this could work) ... Certainly using another app is fine. What would be more relevant to the direct issue is that it becomes routine to encrypt and to have encryption installed. See the recent threads on where all the data is being lost - user data is being lost simply because the companies don't protect it. Why aren't they protecting it? Because there are no easy tools that are built in to automatically and easily protect it. Huh? There have been effective tools for protecting data from disclosure for a long time, though it's not clear what good they'd do for a company whose whole business was just selling access to that data for a fee. I'll bet the Choicepoints of the world are pretty careful protecting, say, their payroll and HR records from disclosure. It's just *your* data they don't mind giving out to random criminals. No amount of crypto could have helped this. iang --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: NSA warned Bush it needed to monitor networks
... Obviously any bureaucrat with the authority to categorize something as secret will more or less automatically so stamp any information that passes through his hands, to inflate his importance, and thus his job security and prospects for promotion. I think a bigger issue here is a sort of rational (to the bureaucrat) risk aversity: if he declassifies something and it turns out he's leaked something valuable (in the eyes of his boss), he's in trouble. As long as there's no cost to stamping secret or FOUO on every document his office produces, this is safer for him than any other course of action. Along with this, going through a document to make sure there's nothing secret in there is a lot more work than just classifying it. The same logic works in the private world--how much of the stuff you've seen under NDA was genuinely going to cause a problem to the company that produced it, if someone just posted it to their website? ... This results in top secret information being treated as not very secret at all, as documented by Richard Feynman, which in turn results in ever higher secrecy classifications, more top than top, a process of classification inflation and debasement. I suspect something very similar happens with the watchlists. I wonder how many different layers of watchlist there are by now --digsig James A. Donald --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
From: Joseph Ashwood [EMAIL PROTECTED] Sent: Feb 17, 2005 12:15 AM To: cryptography@metzdowd.com Subject: Re: SHA-1 cracked This attack means that we need to begin the process for a quick and painless retirement of SHA-1 in favor of SHA-256/384/512 in the immediate future and begin further preparations to move to Whirlpool and other hashes in the near future. I say this because with MD5 completely broken, SHA-0 effectively completely broken, and SHA-1 showing big cracks, the entire SHA series is in doubt, and needs to be heavily reconsidered, otherwise we're looking at a continuing failure of hash functions apparently in a yearly fashion until we run out of the SHA series. Yep. The thing that's interesting here is that the more-or-less obvious fallbacks for SHA1 are RIPE-MD160 and SHA256/512. But given the pile of bodies in front of Wang's door already (MD4,MD5, Haval, RIPE-MD, SHA0, SHA1), it's hard to have any confidence at all that RIPE-MD160 will survive long. All the remaining SHA functions are the same, modulo some constants and the wordsize used--SHA512 is just SHA256 using 64-bit words, different constants, and a few more rounds. So there's really only one SHA function left. It's different enough from SHA1 that it's plausible Wang's attacks won't work, but I can't see any really strong reason to trust in that. Whirlpool looks like the best bet for a fallback right now, but it really hasn't seen anything like the amount of analysis I'd like. This is what it looks like when someone develops a new class of attack that breaks a whole bunch of your available cryptographic primitives in a big hurry. Joe --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
From: Steven M. Bellovin [EMAIL PROTECTED] Sent: Feb 15, 2005 11:29 PM To: cryptography@metzdowd.com Subject: SHA-1 cracked According to Bruce Schneier's blog (http://www.schneier.com/blog/archives/2005/02/sha1_broken.html), a team has found collisions in full SHA-1. It's probably not a practical threat today, since it takes 2^69 operations to do it and we haven't heard claims that NSA et al. have built massively parallel hash function collision finders, but it's an impressive achievement nevertheless -- especially since it comes just a week after NIST stated that there were no successful attacks on SHA-1. Well, there *weren't* any a week ago --Prof. Steven M. Bellovin, http://www.cs.columbia.edu/~smb --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Simson Garfinkel analyses Skype - Open Society Institute
From: Adam Shostack [EMAIL PROTECTED] Sent: Jan 29, 2005 12:45 PM To: Mark Allen Earnest [EMAIL PROTECTED] Cc: cryptography@metzdowd.com Subject: Re: Simson Garfinkel analyses Skype - Open Society Institute But, given what people talk about on their cell phones and cordless phones, and what they send via unencrypted email, they are acting like they think their communications are secure in the absence of any encryption. So I don't think adding some 'cryptographic mumbo jumbo' is going to change their sense of security in the wrong direction. One thing most people seem to miss about this, though, is that cellphones and cordless phones are *great* for privacy from other humans who live in your house or work in your office. When you don't want your children to hear a conversation, you can go take the call in the bathroom or in the car while you're driving alone. Everybody seems to miss this--cellphones and cordless phones don't diminish privacy, they just move it around. Sophisticated eavesdroppers can violate more of your privacy, but nosy family members, roommates, and office mates can violate a lot less. I thnk most people correctly evaluate which of these groups is more likely to do something unpleasant with what they learn by eavesdropping. It seems to me that VOIP pushes this in a somewhat different direction, because it's probably easy for your high-speed internet access (maybe a wireless hop to a router that talks to a cable modem) to be eavesdropped by moderately technically savvy nosy neighbors, and because there are a lot of criminals who are using more technology, and will surely target VOIP if they think they can make any money off it. Adam --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Entropy and PRNGs
From: John Denker [EMAIL PROTECTED] Sent: Jan 10, 2005 12:21 AM To: David Wagner [EMAIL PROTECTED] Cc: cryptography@metzdowd.com Subject: Re: Entropy and PRNGs Conditioned on everything known to the attacker, of course. Well, of course indeed! That notion of entropy -- the entropy in the adversary's frame of reference -- is precisely the notion that is appropriate to any adversarial situation, as I have consistently and clearly stated in my writings; see e.g. the end of the definitions section, i.e. http://www.av8n.com/turbid/paper/turbid.htm#sec-defs ... Actually, I think Ben got it right. Entropy depends on context. The attacker might have extra context that allows him to narrow down the possible values of the randomness samples. Heed your own of course statement. It is hard to imagine a situation where my adversary has more context about my generator than I have myself. Well, the broader problem isn't the context, it's the model. If your attacker (who lives sometime in the future, and may have a large budget besides) comes up with a better model to describe the process you're using as a source of noise, you could be out of luck. The thing that matters is H(X| all information available to the attacker), which is based on P(X | all information available to the attacker), which includes a model that may be better than yours. But I think it's of practical value to consider the different attackers whose information might not include some information you use for seeding a PRNG. Some sources of entropy, such as packet arrival times, are not worth much for attackers on your local network who are attacking you in real time, but are quite valuable against attackers who attack you later. Other sources of entropy, such as the hash of the contents of your Windows registry, or a full directory tree from your hard drive, are worthwhile against real-time attackers without access to your machine, but worthless against attackers with your machine in their hands. Using cheaply-available sources of each kind in seeding a PRNG decreases the set of attackers that will be able to attack you, while not preventing you from also using some source of entropy you believe to be good against all attackers. ... If you want people to believe that unconditional entropy is a worthwhile concept, you'll have to come up with a nontrivial application for it. Differentiate between measures of entropy. Collision entropy (Renyi entropy of order two) is very useful in determining how many samples you can take before expecting a collision, and it's not conditioned on an attacker's information. And collision probabilities do matter, in both obvious and subtle ways, for PRNG security. --John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion (was: SSL/TLS passive sniffing)
From: John Denker [EMAIL PROTECTED] Sent: Jan 5, 2005 2:06 PM To: Enzo Michelangeli [EMAIL PROTECTED] Cc: cryptography@metzdowd.com Subject: Re: entropy depletion (was: SSL/TLS passive sniffing) ... You're letting your intuition about usable randomness run roughshod over the formal definition of entropy. Taking bits out of the PRNG *does* reduce its entropy. This may not (and in many applications does not) reduce its ability to produce useful randomness. Right. The critical question is whether the PRNG part gets to a secure state, which basically means a state the attacker can't guess in the amount of work he's able to do. If the PRNG gets to a secure state before generating any output, then assuming the PRNG algorithm is secure, the outputs are indistinguishable from random. The discussion of how much fresh entropy is coming in is sometimes a bit misleading. If you shove 64 bits of entropy in, then generate a 128-bit output, then shove another 64 bits of entropy in, you don't end up in a secure state, because an attacker can guess your first 64 bits of entropy from your first output. What matters is how much entropy is shoved in between the time when the PRNG is in a known state, and the time when it's used to generate an output. --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
From: Ben Laurie [EMAIL PROTECTED] Sent: Dec 22, 2004 12:24 PM To: David Wagner [EMAIL PROTECTED] Cc: cryptography@metzdowd.com Subject: Re: The Pointlessness of the MD5 attacks ... Assuming you could find a collision s.t. the resulting decryption looked safe with one version and unsafe with the other (rather than gibberish), which I find an even bigger stretch than the idea that you could find a block that looked safe in one version and unsafe in another, I would have said that the mere fact of using a pointless decryption to control the action of the code would be suspect. Hmm. So maybe I'm missing something. Here's my scenario: a. Alice decides to use GOST for encryption. She finds an implementation in C from Eve, which includes the S-boxes hard-coded in. Note that the specific S-boxes used for GOST are potentially pretty important for their security. b. She also finds a review from some well-known cryptanalyst, Bob, discussing the requirements on the S-boxes, and verifying that the above implementation uses good S-boxes, which includes the md5 hash of the C source code. c. Alice downloads the C source code, and checks the md5 hash. Since the hash is correct, she compiles the code, and starts using her known-secure version of GOST to encrypt sensitive data. d. Unknown to her, though, Eve has slipped in a changed version of the C source code, with the S-boxes changed in a way that makes the encryption much weaker. What prevents this attack from working? Alice counts on a review done by someone competent and a hash of the source code, but the weakness of the hash function means that she's vulnerable to an attack. The only thing that might keep it from working is if it happens to be impossible to choose a pair of sets of S-boxes so that one is weak, the other is strong, and the pair allows an md5 collision. I don't know whether this is possible or not, but there's no inherent reason to think it's impossible--just making some of the 4-bit wide S-boxes in GOST non-bijective has pretty big security implications. (Though 32 rounds covers a lot of sins in S-box selection, in terms of practical attacks rather than academic ones.) ... Indeed. Not the point I am making. In a nutshell, yes, it is scary that Wang found collisions. No, it is not _more_ scary that you can use those collisions to fool people who aren't looking anyway. I think you can use them in ways that may fool people who *are* looking. All you need is a legitimate reason to have a more-or-less arbitrarily chosen block of bits in a part of your program, and then the person reviewing the code says okay, that's random-looking, but reasonable enough. As an alternative example, consider embedding a large prime number in your code, to be used as the modulus when you're doing Diffie-Hellman. Someone reviews the code, and verifies that the number is prime and has all the other required properties. Then, you swap in a different bitstring of equal length, but which is composite and yields a reasonably easy attack on Diffie-Hellman. What prevents this? Ben --John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
From: Ben Laurie [EMAIL PROTECTED] Sent: Dec 14, 2004 9:43 AM To: Cryptography [EMAIL PROTECTED] Subject: The Pointlessness of the MD5 attacks Dan Kaminsky's recent posting seems to have caused some excitement, but I really can't see why. In particular, the idea of having two different executables with the same checksum has attracted attention. But the only way I can see to exploit this would be to have code that did different things based on the contents of some bitmap. My contention is that if the code is open, then it will be obvious that it does something bad if a bit is tweaked, and so will be suspicious, even if the something bad is not triggered in the version seen. So, to exploit this successfully, you need code that cannot or will not be inspected. My contention is that any such code is untrusted anyway, so being able to change its behaviour on the basis of embedded bitmap changes is a parlour trick. You may as well have it ping a website to find out whether to misbehave. So, are you sure there can never be a program which allows such an exploit? I've seen programs that had embedded components (state machines in particular) which were not easily human-readable, and had themselves been generated by computer. And even large graphics, sound, or video sequences can really change the meaning of a program's actions in some ways; those might be susceptible to the requirements of the attack. I agree it's hard to see how to exploit the existing MD5 collision attacks in programs that would look innocent, but I don't see what makes it *impossible*. Then you have data files, as Adam Back mentioned, which are often not human readable, but you'd still like to know if the signature on them is valid, or if they've been changed surreptitiously since the last time they were checked over. Finally, I'm very skeptical that the attacks that have been found recently are the best or only ones that can be done. Do we have any special reason to think that there will never be a way to adapt the attack to be able to slip something plausible looking into a C program? Once your hash function starts allowing collisions, it really just becomes a lot less valuable. Cheers, Ben. --John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Blinky Rides Again: RCMP suspect al-Qaida messages
From: Adam Shostack [EMAIL PROTECTED] Sent: Dec 11, 2004 4:52 PM Subject: Re: Blinky Rides Again: RCMP suspect al-Qaida messages ... It seems consistent that Al Qaeda prefers being 'fish in the sea' to standing out by use of crypto. Also, given the depth and breadth of conspiracies they believe in, it seems that they might see all us cryptographers as a massive deception technique to get them to use bad crypto. (And hey, they're almost right! We love that they use bad crypto.) They're going to have the same problems as the rest of us using strong cryptography--configuration and usability problems, key management hassles, incompatibilities between versions and programs, etc. They have to do this with no central authority, no single support line or person who can reliably start things up and help them, in a basically decentralized way. The cypherpunkish idea of a decentralized conspiracy using strong crypto only works if either the tools are a lot easier to use, or if the conspiracy is made up of cryptographically sophisticated people. AQ is presumably made up of people who know a lot about the Koran, and probably a lot about day-to-day operational security against the Pakistani or Indonesian secret police, but there's not much reason to think they are very sophisticated about cryptography. If you can't get most computer-literate people you know to use PGP to send you e-mail, how well is it going to work to do with a bunch of random jihadis? -John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: MD5 To Be Considered Harmful Someday
From: James A. Donald [EMAIL PROTECTED] Sent: Dec 7, 2004 6:57 PM To: [EMAIL PROTECTED] Subject: MD5 To Be Considered Harmful Someday But even back when I implemented Crypto Kong, the orthodoxy was that one should use SHA1, even though it is slower than MD5, so it seems to me that MD5 was considered harmful back in 1997, though I did not know why at the time, and perhaps no one knew why. The pseudocollision on MD5 paper was published in 1994, and Doebbertin's full collisions for MD5's compression function were published in 1996, so there was plenty of reason by 1997 to want to move to a different hash function. People who stuck with MD5 for collision resistance after that were demonstrating seriously bad judgement, since the only argument left for MD5's security was well, but nobody's published a way to exploit the attack on full messages yet. James A. Donald --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Gov't Orders Air Passenger Data for Test
News story quoted by RAH: WASHINGTON - The government on Friday ordered airlines to turn over personal information about passengers who flew within the United States in June in order to test a new system for identifying potential terrorists. The interesting thing here is that they can't really test how effective the system is until they have another terrorist event on an airline. Otherwise, they can assess the false positive rate of their list (people who were on the no-fly-list, shouldn't have flown according to the rules, but did without trying to hijack the plane), and the false positive and false negative rate of their search for names in the list (e.g., when it becomes obvious that Benjamin Ladon from Peoria, IL would have matched, but wasn't the guy they were hoping to nab, or when it becomes obvious that a suspected terrorist was in the data, did fly, but wasn't caught by the software). The system, dubbed Secure Flight, will compare passenger data with names on two government watch lists, a no fly list comprised of people who are known or suspected to be terrorists, and a list of people who require more scrutiny before boarding planes. Presumably a lot of the goal here is to stop hassling everyone with a last name that starts with al or bin, stop hassling Teddy Kennedy getting on a plane, etc., while still catching most of the people on their watchlists who fly under their real name. ... Currently, the federal government shares parts of the list with airlines, which are responsible for making sure suspected terrorists don't get on planes. People within the commercial aviation industry say the lists have the names of more than 100,000 people on them. This is a goofy number. If there were 100,000 likely terrorists walking the streets, we'd have buildings and planes and bus stops and restaurants blowing up every day of the week. I'll bet you're risking your career if you ever take someone off the watchlist who isn't a congressman or a member of the Saudi royal family, but that it costs you nothing to add someone to the list. In fact, I'll bet there are people whose performance evaluations note how many people they added to the watchlist. This is what often seems to make watchlists useless--eventually, your list of threats has expanded to include Elvis Presley and John Lennon, and at that point, you're spending almost all your time keeping an eye on (or harassing) random harmless bozos. R. A. Hettinga mailto: [EMAIL PROTECTED] --John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
A new academic hash result on the preprint server
Guys,
Bruce and I have a new result on hash function security, which uses Joux'
multicollision trick in a neat way to allow long-message second preimage
attacks. We've posted it to the e-print server.
The basic result is that for any n-bit hash function built along the lines of
SHA1 or Whirlpool (e.g., using an n-bit compression function and Damgard-Merkle
strengthening), we can mount a second preimage attack on long messages for a
lot less than 2^n work. For a 2^k message-block message, we do about 2^{n-k+1}
work (when kn/2) to get a second preimage. We also have a little cheaper way
to find a kind of goofy set of multicollisions than Joux gives.
None of this result leads to a practical attack on anything, as far as I can
see. The messages that are vulnerable are impractically long, and there's
never an attack cheaper than offline collision finding. But I think this
result raises some kind-of interesting questions about the security of hash
functions between the 2^{n/2} bound for collision finding and the 2^n bound for
first and second preimage finding.
Comments appreciated,
--John
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
