Wikipedia:Reference desk/Archives/Mathematics/2014 April 16

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 16

md5 preimage attack question

so our article on md5 says under Preimage vulnerability, "On April 2009, a preimage attack against MD5 was published that breaks MD5's preimage resistance. This attack is only theoretical, with a computational complexity of 2^123.4 for full preimage."

I don't understand this at all. The MD5 article calls it a 128-bit algorithm. So how does a 2^123.4 complexity attack "break" MD5? Doesn't this represents just 4.6 bits of complexity (128-123.4), i.e. 25-fold reduction in the search space? If twenty five million computers can do it exhaustively, it is already broken, who cares if a million can do it in the weakened form instead? I wouldn't call that "breaking preimage resistance" at all, since it is broken even if twenty five million computers can do it... Even a billion shouldn't be able to do it, or a hundred billion... It should take more computers than there are atoms in the Universe....

Or is it "broken" on the assumption that if you can reduce the search space by even a factor of 0.0005, then it is no longer a secure hash? If this is the case then is that because 1) of the 'theoerical' meaning of secure, i.e. if you only need to search 45783897348972489127348975190342562347892385778462378461793486287434678214691278346812793478346286284726134781622 out of 45783897348972489127348975190342562347892385778462378461793486287434678214691278346812793478346286284726134781623 possibilities (trailing 2 instead of 3) then it is broken since you didn't need to look at one of the possibilities. Or is this 2) beacause it's considered inevitable that if a reduction is found now, further ones will be found in the future? So that it's still "secure" now but this is expected to change in the future?

Any explanation would be appreciated. — Preceding unsigned comment added by Cryptoguy321 (talk • contribs) 13:22, 16 April 2014 (UTC)

I think it is both 1) and 2). Any reduction in the search space qualifies as a publishable attack, and even a small reduction is worrying since it suggests there are weaknesses in the design that could lead to practical attacks later. I changed "breaks" to "weakens" in the article. -- BenRG (talk) 19:02, 16 April 2014 (UTC)

I changed it back to "break". An attack doesn't have to be immediately practical to be considered a break: it's a break because it breaks security assumptions about the search space by several orders of magnitude. —SeekingAnswers (reply) 01:29, 20 April 2014 (UTC)

1) Depends. If there is only a small exceptional set, I wouldn't call it broken. Using one additional bit (129 rather than 128) would more than offset that kind of weakness.

One implementation of RSA (basic scheme: x is encoded as x^pub mod n, and (x^pub)^priv mod n equals x) used an exponent of pub = 1. That flaw didn't get fixed until somebody noticed how "unbelievably fast" the code was at calculating (x^pub)^priv mod n ! That was "broken."

There might however be concerns like BenRG's. Which takes me to...

2) There might be ways to find

a) more spaces you can exclude by slight variation of the method used. The remaining space which "survives" could be too small to be regarded safe.

b) a much bigger space by strengthening the original attack in some way. This is BenRG's idea of a practical attack. Some problems could be reduced to almost trivially low bounds. The one I know about is not cryptographic, and its actual bound in a practical range is not extremely low, but its asymptotic bound is: PRIMES is in P.

c) a whole class of spaces by generalizing the original approach in some ingenious way. This is less likely, but if any class is found, any individual case (or even worse, any group of individual cases?) only has to be tested against a low number of spaces. The average would be 1 + 0.04 + 0.0016 + ... < 1.042 if the spaces are not too correlated. - ¡Ouch! (^{hurt me} / _{more pain}) 11:44, 17 April 2014 (UTC)

bit commitment scheme

Hi,

I don't really understand the point of "commitment scheme"? In the rock-paper-scissor example used to introduce it, can't Alice and Bob just encrypt their choice with any algorithm (symmetric or asymmetric) then give each other then encrypted versions. Once they both have the encyrypted versions they can give each other the key.

What's wrong with this? If you have something encrypted with one PGP key, for example, you can't get a different valid plaintext back by giving out any private key other than the one you encrypted with... (since it only has two prime factors). you are fully "committed." Cryptoguy321 (talk) 14:40, 16 April 2014 (UTC)

I think giving them the key after the encrypted info is a form of a commitment scheme, whereas giving them the key first would not be. Also note that if you give them the key by the same communication channel as the encoded message, then, if that communication channel is compromised, then anyone can decipher the code. For this reason you might want to use two keys, one they were given in advance, via a secure channel, and one they get after the encoded messages have been sent. StuRat (talk) 14:52, 16 April 2014 (UTC)

Encryption is not the same as a commitment scheme. This is the crux of the OPs question. Shadowjams (talk) 04:06, 18 April 2014 (UTC)

Your suggested use of encryption and key swapping is itself a type of commitment scheme. From the article you linked:

“ A way to visualize a commitment scheme is to think of the sender as putting the value in a locked box, and giving the box to the receiver. The value in the box is hidden from the receiver, who cannot open the lock themselves. Since the receiver has the box, the value inside cannot be changed—merely revealed if the sender chooses to give them the key at some later time. ”

--But the dedicated schemes available are designed to not require so much human intervention and waiting, and are optimized for that specific task. In contrast, encryption schemes are designed for a totally different purpose. Stu is getting at key distribution, which is yet another separate problem, for which other schemes have been developed. Basically, different goals are served by different tools. I can drive nails into wood with my heavy screwdriver, but I prefer to use a hammer. SemanticMantis (talk) 16:27, 16 April 2014 (UTC)

Encryption keys alone are not sufficient to prove message integrity. For example... if you symetrically encrypt something using a one time pad, and you are later revealed "a key" (not necessarily the key), you can make the revealed plaintext whatever you want it to be if you control the "key". Hash functions like the SHA family are specifically designed against this sort of problem... not all encryption algorithms are. That said, there's something called MDC that uses exactly this approach. And on the flip side, AES (and other symetrical key algorithms) have often been used as primatives for hash functions. So practically speaking it's not that nuts. But there is a big fundamental difference between the two. Your example using PGP is much more complicated because PGP (or GPG) uses all three of these... GPG symetrically encrypts the message, asymetrically encrypts the key, uses a salt on the former, and then checks the integrity on all of them. So your PGP example doesn't map to the more general question of "isn't encryption enough". This is not to mention all the various bit swapping attacks against block-based encryption. Shadowjams (talk) 04:06, 18 April 2014 (UTC)

Good point that one-time-pads can allow for ANY desired plaintext! However, I'm not sure that property applies to most common schemes used today... it seems that the key points here are that the goals of encryption and commitment are different, though sometimes those goals can be accomplished by using similar tools. SemanticMantis (talk) 13:55, 19 April 2014 (UTC)

Cryptographic primitives are designed to provide specific security properties, such as confidentiality, authenticity etc. Assuming that a primitive that provides one security property (confidentiality) provides some other property (commitment) can fail spectacularly, as illustrated above with the one-time pad. If a primitive is to be used for a property that it has not been assessed for (in this example seeking commitment from a primitive that is intended to provide confidentiality with the least size of key), the protocol must be carefully designed. Just saying that AES can be used for commitment does not address the protocol for its use for this purpose. For example, if I commit a value as the first 32 bits of the plaintext of an AES-encrypted block, I can in a relatively short space of time find a key that with produce any desired value from a given ciphertext. This essentially implies that encryption and authentication properties are required simultaneously, which most encryption primitives do not provide. A commitment scheme might also need assurances that the scheme is robust against various attacks, e.g. a man-in-the-middle attack. —Quondum 15:03, 19 April 2014 (UTC)