0
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ possible specialized duplicate of Do parts of a hash carry the properties of the entire hash? $\endgroup$
    – Thomas
    Commented Oct 26, 2012 at 14:51
  • 1
    $\begingroup$ 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). $\endgroup$
    – fgrieu ♦
    Commented Oct 26, 2012 at 15:23
  • 1
    $\begingroup$ @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. $\endgroup$
    – fgrieu ♦
    Commented Oct 26, 2012 at 20:47
  • 1
    $\begingroup$ @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). $\endgroup$
    – Paŭlo Ebermann
    Commented Oct 26, 2012 at 22:53
  • 1
    $\begingroup$ @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$. $\endgroup$
    – fgrieu ♦
    Commented Oct 27, 2012 at 15:16

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What is the today safe $n$ that make it impossible for an attacker to brute force in a "reasonable" time?Something greater than $80$ ? $\endgroup$
    – curious
    Commented Apr 15, 2013 at 10:06
  • $\begingroup$ $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.) $\endgroup$
    – Nova
    Commented Dec 5, 2014 at 8:58
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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