4

I am doing a project on cracking sha256 using rainbow tables. I am trying to attack 8 digit alphanumeric sequences. I understand exactly how rainbow tables work and how the chains are supposed to be formed and stored. However, I do not understand how to get a reducing function to form the chains. I have googled and thought about it myself for hours, with no results. So, what is a good reducing function for the chains and how can it prove that it covers all 8 digit alphanumeric sequences.

Rishab Mehra
  • 159
  • 2
  • 9
  • 1
    This question appears to be off-topic because it is about developing cryptanalysis techniques and doesn't include a programming question. – Duncan Jones Oct 31 '14 at 08:59
  • 3
    @Duncan One could argue that it is a question about a software algorithm, which is on-topic according to the help center. Stack Overflow is not only for programming questions. – Niklas B. Oct 31 '14 at 11:45

1 Answers1

3

There are 10^9 distinct sequences of 8 digits. There are 1073741824 possible values for the first 30 bits of a SHA256 hash value. So one reasonable approach would be to extract those 30 bits and use that number modulo 10^9 as your reduction function:

R(hash) = hash[0:30] % 10^9

It is unlikely that this actually covers all 8 digit sequences, but in practice it should definitely good enough due to assumed "randomness" properties of SHA256. There is a small bias towards numbers <= 2^30 - 10^9 though because of the modulus.

Niklas B.
  • 92,950
  • 18
  • 194
  • 224