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.

I am doing some research on cryptography, so I generated a random string of numbers resembling a creditcard number(according to MOD10 validation) and encrypted it with SHA1 algorithm for encryption. But to make this interesting, I decided to make my database column size exactly 2/3 smaller than the encrypted text so that it is truncated on save. So now I have in my database 2/3 of a SHA1 hash, and I want to reverse engineer it so I can recover my original full hash.

Things to consider:

  • I also saved the original hash just for final comparison purposes
  • To make things easier on me and give more possibilities, I saved the creditcard generated as a masked number in the format 000000****0000(for whatever use you can think of that will help)
  • I didn't post any code since it is irrelevant and unnecessary to this question.
  • This is not just a regular SHA1 algorithm. I tweaked it the procedure before to add some variables like current time and other variables to original encrypted number, in order to make that if you encrypt the same word twice in a row, both results won't be equal(as a matter of fact, I tested it with over 100k encryptions in a row and not a single hash was equal to the first one generated, even though the words encrypted were the same), but you can get the original value out of both of them nonetheless.
  • I have access to the certificate that controls the encryption, so the hardest part is theoretically past behind, right?

Anyways... my question is how to recover the hash for the creditcard number generated before, knowing that I got the first 2/3 of the hash and the certificate used to create it? Is brute force the only available or possible solution?

share|improve this question
    
possible specialized duplicate of Do parts of a hash carry the properties of the entire hash? –  Thomas Oct 26 '12 at 14:51
1  
This question needs improvement, badly. First sentence use "encrypted it with SHA1", akin to "drilled with a hammer". Fragment "the certificate that controls the encryption" does not parse. OP "saved the original hash" but only "(has) in (his) database 2/3 of a SHA1 hash". A SHA-1 hash is 160 bits, not divisible by 3. Two infos are missing: how many **** there are, and exactly what is hashed. The alleged "research on cryptography" commands exact vocabulary, lack thereof suggests homework (which is acceptable) or request for help to crack a real system (which I frown upon). –  fgrieu Oct 26 '12 at 15:23
1  
@leobelones: ah, howmework in disguise. Hint: if I understand the statement correctly, the best attack has cost $O(10^s)$ where $s$ is the number of stars. –  fgrieu Oct 26 '12 at 20:47
1  
@fgrieu: I can think of one with $10^{s-1}$ SHA-1 calls (and some comparisons and one modulo operation) (this is still $O(10^s)$, though). –  Paŭlo Ebermann Oct 26 '12 at 22:53
1  
@PaŭloEbermann: you improved my attack by using known redundancy in an unknown. We now get an expected cost next to $10^{s−1}/2$ SHA-1 hashes for all reasonable number of stars $s$. –  fgrieu Oct 27 '12 at 15:16
show 1 more comment

1 Answer

First off, hashing is not encryption. Those are two very different concepts. You should read those links, they'll help you understand:

As for your original question: What happens to the security of SHA-1 when truncated?

Here is an answer that's true for all hash functions:

In general using a hash function $H:\{0,1\}^\ast\to\{0,1\}^n$ you expect:

  • $2^n$ work to find a preimage
  • $2^n$ work to find a second preimage
  • $2^{\frac{n}{2}}$ to find a collision

Notice these numbers depend solely on the size of the range of your function. By truncating you make the range smaller so your security expectations are lowered by that much and also any existing cryptanalysis technique will probably work better against your truncated function since you have more degree of freedom.

I'm still very confused by the way you're confusing the hashing, encryption and certificate notions.

share|improve this answer
    
What is the today safe $n$ that make it impossible for an attacker to brute force in a "reasonable" time?Something greater than $80$ ? –  curious Apr 15 '13 at 10:06
add comment

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.