Recovering SHA1 knowing 2/3 of the hash generated

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?

• possible specialized duplicate of Do parts of a hash carry the properties of the entire hash? – Thomas Oct 26 '12 at 14:51
• 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
• @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
• @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
• @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

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.

• 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
• $n = 80$ would mean that a collision attack only needs $40$ "bits of work". That's not secure. The output size of SHA-1 should be the absolute minimum for general security. ($160$ bits.) – Nova Dec 5 '14 at 8:58

Because you are mutating and throwing in indeterminate data such as timestamps, this is not going to be possible.

We generally do not try and recover a hash, unless for forensic purposes, and if this is foreseeable, you may want Reed Solomon error correction.

What we can do for determinate hashes:

Since credit cards must satisfy the Luhn algorithm (not mod 10), we pad the truncated hash with filler, usually x'00', and brute force for a minimum width of 15 (Amex) and maximum width of 16 using a numeric character set.

1. Pad the truncated hash to full length with nulls.
2. Crack with brute force comparing truncated (not stopping on first found).
3. Test each number for Luhn compliance.
4. Optionally filter out invalid or non-important BIN/Product (first 4/6 digits).
5. Re-hash the result to find the missing tail.

N.B. Credit card numbers are short, collisions are extremely unlikely, but in the event that two (or more) results are found, there may be other means of intelligently guessing which is the most likely but no way to be sure

Your mask will only go so far, as the cardinality of those first 6 digits is very poor, for a given bank the first four are the same, the next two are usually sub products. This is why card numbers are recycled.

2/3 is one thing, but cutting back to 3 or even 4 bytes will increase this risk, it may as well be CRC when it gets that short....

Apologies for coming in late, but I am keen on these things.