0
$\begingroup$

I have a task to find a the message for which the SHA-1 hash's last 11 symbols in hexadecimal presentation corresponds to an 11-digit number.

I have been given the following example solution:

For the code 38607310235, a solution is a513b8c4507ea2891fb34cd4612e038607301235, which is the hash of $y$

How can I find $y$?

Improve this question
$\endgroup$
8
  • $\begingroup$ I'm not sure what you're asking. I think the problem you're describing is: Given an 11 digit number, find a string who's SHA1 hash ends with those 11 digits when written in hex. Is that correct? $\endgroup$
    – Cryptographeur
    Commented Nov 27, 2013 at 17:33
  • $\begingroup$ Yes I think so. Thanks for the answer. The question is how the last 11 digits of the hash are associated with the initial number 38607310235. $\endgroup$
    – Kirill Ryzhkov
    Commented Nov 27, 2013 at 17:35
  • $\begingroup$ Well, because they're equal to it? That association is clear enough. Less clear is what that is the hash of. Its not hard to create a string of 40 characters that end with 11 of your choosing. $\endgroup$
    – Cryptographeur
    Commented Nov 27, 2013 at 17:37
  • $\begingroup$ Maybe I am getting something wrong but why in the example solution of the 38607301235 its hash is a513b8c4507ea2891fb34cd4612e038607301235 with 38607301235 at the end? If you try to convert 38607310235 its hash will be 6502c8f9f5c222b9598d4e074fd3431f506948bc. What am I missing? $\endgroup$
    – Kirill Ryzhkov
    Commented Nov 27, 2013 at 17:41
  • $\begingroup$ But how do I create 40 characters that end with 11 of your choosing? I have no idea. Can you help with this? For example if I take this number 32945678000. $\endgroup$
    – Kirill Ryzhkov
    Commented Nov 27, 2013 at 17:44

2 Answers 2

Reset to default
2
$\begingroup$

Evaluating, we have that

Sha_1(38607310235)=6502c8f9f5c222b9598d4e074fd3431f506948bc

So, I'm guessing the question you're actually asking is:

Given an 11 digit number $x$, find $y$ such that $L[H(y)]=x$, where $L(\cdot)$ takes the last 11 hexadecimal characters, and $H(\cdot)$ is the SHA-1 hash function

This problem is believed to be hard to do, so I'm guessing than explicitly finding such a value you're hoping to work out how long it would take to find one. There are collision attacks on SHA1, but I don't know of any preimage attacks, and from the comments I'm think its unlikely that you're expected to use one. So, let us consider the problem:

How many calls to $H(\cdot)$ must I make to get one who's output ends with a chosen set of 44 bits (=11 hex)

Consider the probability that a call of $H(x)$ with a random input has the required form. Well, there are lots of bits we don't care about, but there's only a $1/2$ chance that we 'get lucky' for each of the 44 bits we care about. So, we should expect it to take $2^{44}$ attempts before we find some $x$ such that $H(x)$ ends in the 'right' values.

Note that even in this answer we've glossed over how one might choose an input at random.

The question as currently previously written says said:

find one of the messages, which SHA-1 hash last 11 symbols in hexadecimal presentation corresponds to 11-digit number with an example solution.

Sure! You can just make up any 29 hex symbols and you'll [almost certainly] get something valid for the problem you state. So, as per the example in comments:

  32945678000  -> baadf00dbeefcafefeedbabef00d132945678000
  32945678000  -> 0000000000000000000000000000032945678000

Why is this? Well, it is believed that the image of SHA is the whole of ${0,1}^{160}$, and as a result any string from there should be the image of something when encrypted under SHA. The hard bit of this problem is trying to find what on earth the preimage of this value would be under the SHA1 hash function - and for this I don't have any answer whatsoever. Finding a preimage for the particular values I've given you (which you'll notice are overly structured!) is currently believed to be a very difficult problem.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks, but still I am confused how you got baadf00dbeefcafefeedbabef00d132945678000. Can you explain this in depth? $\endgroup$
    – Kirill Ryzhkov
    Commented Nov 27, 2013 at 17:56
  • $\begingroup$ So does it mean that I can type 29 random hex symbols? $\endgroup$
    – Kirill Ryzhkov
    Commented Nov 27, 2013 at 18:02
  • $\begingroup$ to get A possible hash ending in the 11 characters you demand you. However, you won't know what it is the hash of (and so couldn't prove it was a possible hash even though probability says it will be) $\endgroup$
    – Cryptographeur
    Commented Nov 27, 2013 at 18:03
  • $\begingroup$ But is it possible to find all possible hash endings for a demanded number? $\endgroup$
    – Kirill Ryzhkov
    Commented Nov 27, 2013 at 18:07
  • $\begingroup$ Yes: its all possible values for the first 29 characters. Warning: I really don't think you've managed to ask the question that you're trying to solve. I hope Owlstead & I have answered the ones you have asked, but I don't think its what you're trying to do. $\endgroup$
    – Cryptographeur
    Commented Nov 27, 2013 at 18:18
3
$\begingroup$

There is no why it is identical. The input form of the data does not influence what the output of a secure hash function should look like. The input of a hash should be unrelated to the output except for the mapping performed in the hash function itself. There should be no method of calculating the output other than to execute the hash function.

The best way to find another hash with the same property is to brute force it; go through a lot of numbers, convert them to bytes, calculate the hash and compare against the hexadecimal representation of the output. As each hexadecimal digit represents 4 bits, you would have to perform $2^{44}$ calculations (as I don't see how the birthday paradox would help you here). Note that, as CodesInChaos mentioned in a comment, that rainbow tables could speed up searches for cases where the input has properties that are reflected in the output.

If you get the wrong hash output, then it is likely that your conversion from the given number to bytes is failing. You may want to try another encoding.

Improve this answer
$\endgroup$
5
  • $\begingroup$ About that last sentence: only if you know the hash to be over the data of course. $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 27, 2013 at 19:36
  • $\begingroup$ Searching a fixed 44 bit space might actually be one of the rare situations where a rainbow table is useful. $\endgroup$
    – CodesInChaos
    Commented Nov 28, 2013 at 13:25
  • $\begingroup$ @CodesInChaos True, but you would of course still need the same amount of calculations to build the rainbow table. We are are looking for a 1:1 pair, not a collission. Or am I missing something? $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 28, 2013 at 14:51
  • $\begingroup$ I don't get your point regarding collisions. But 2^44 should be feasible as a one-time effort, the rainbow table is only used to make additional conversions cheaper. $\endgroup$
    – CodesInChaos
    Commented Nov 28, 2013 at 14:54
  • $\begingroup$ @CodesInChaos Actually, I think we are not the same page, so I'll edit the rainbow table comment into the answer and delete some comments, otherwise we'll run out of the page :) $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 28, 2013 at 15:50

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.