Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

The best way to ask this question and have a concrete answer is to set a very specific example. This is the example I would be interested in reading an answer to:

Consider that my friend Alice has several (~5) hard drives encrypted with Truecrypt. Alice is using AES (256-bit, 14 rounds) with RIPEMD-160. I could see that she has a script for mounting the different drives -I guess that because she's pretty lazy and just wants to type in one password. Of course, every disk is salted differently, etcetera.

From her script, I can figure out that the password for each drive comes from concatenating a common string (for all drives) with a fixed string set in the script (different for every drive). I don't know the length of the common string (it's user typed), but the fixed strings are like 6-10 characters long.

Let's then first assume that I don't know the common part of the password, but I know the fixed part for every disk because I see it in the script.

So the question is, and don't be afraid of diving into explaining the mathematical reason- how insecure is the fact that she uses a common string, and how could I attack that flaw?

And secondly, what if I didn't know the fixed part for every hard drive but I knew that they begin with the same common part (which value is unknown too)?

share|improve this question
add comment

1 Answer 1

If I know your password is k bits long and I know the m bits, then I have to brute force the rest of the k-m bits. That's the standard for any algorithm and independent of whether this is prefix, suffix etc. This means that I have $2^{k-m}$ tests to make.

However, you can even do better, You can say that you have a decayed version of the key, or you have partial key exposure, you have some plaintexts and the according ciphertexts. In this scenario, there are several effective attacks, even for AES, with different approaches, even SAT solvers. Have a look at the following papers:

Of course there are limitations as you can see from the papers, but depending on how much bits you want to crack, it might be easier to go this way than brute force them.

share|improve this answer
    
Ah! :D Ok, forget about knowing the fixed part. The important part of the question is, what if I just know that there are bits from the passwords (that are used to generate the key) that are common in several systems, even if I don't know their values? I just know that they share a prefix... Is that exploitable? I tend to think that it has to be... –  huff Feb 14 at 21:49
    
(after a first gaze of the papers you put): ...and let's assume that I can't use cold-boot attacks or anything... she unplugged that computer days ago. –  huff Feb 14 at 21:58
    
Theoretically, I'd also agree with you, however, I haven't seen a lot of work on that. I believe that with SAT solvers you could do something like that, but you would need a lot of data and coffee... For public key though, there are some attacks. e.g. for a RSA-like cryptosystem (not actual) you could have a look at this one: May, Alexander, and Maike Ritzenhofen. "Implicit factoring: On polynomial time factoring given only an implicit hint." Public Key Cryptography–PKC 2009. Springer Berlin Heidelberg, 2009. 1-14. For symmetrics systems I don't remember reading any. –  absinthe Feb 14 at 21:59
    
I tend to think that, even if the different disks had been encrypted with a key generated under different conditions (i.e. salted differently, etc), there has to be a (complex) way to limit the number of brute force attacks -because of the fact that the passwords have some bits in common, there has to be a way to statistically discard a set of keys. And I would say that it has more to do with the hashing than the encryption algorithm. Makes more sense... even though I could imagine that both would have to be considered in the hypothetical attack. –  huff Feb 14 at 22:06
    
However, I'd say that the point of cold boot attack is not that you will have to recover the bits from RAM, but as you said you will have some part of the key. You could read the rest of the paper disregarding the cold-boot scenario, but thinking that you have the bits in specific posiotions (prefix, suffix, etc) –  absinthe Feb 14 at 22:07
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.