Thomas Pornin does his crypto thing. – Conversation in The DMZ

Conversation started Oct 26, 2011 at 21:01.

this.josh

Oct 26, 2011 21:01

Does that mean that the chains are ring subsets of the domain?

maybe they don't have addative identity though.

Jeff Ferland

@thisjosh I was all like, "I didn't see that when... when did we get math markup? Oh, it's not security, it's crypto."

this.josh

Heh, yeah, it scares people off. I don't think we want to bring it over here.

I think that is the origin of "It's all Greek to me" comes from.

Despite what people may claim, reading massive volumes of documents will not necessarily provide you with the data you need.

Thomas Pornin

Oct 26, 2011 21:21

@thisjosh The chains in a rainbow table do not have an algebraic structure which could be called "ring".

Actually, the operation which goes from one link to the next within a chain involves calling the hash function H, and that function is supposed to lack such structure.

this.josh

Oh, oops, there is not identity, I though they had multiplicative identity

Thomas Pornin

Otherwise, we would not bother building a rainbow table, we would just attack the algebraic structure for the function.

this.josh

I was thinking that chain collision would return you to the first element instead of the last element in the chain.

Thomas Pornin

A rainbow table can be viewed as a compression scheme. We can arrange for pairs (password,hash) to be recomputable in a chain way, so that we can store the whole chain by storing only the start and end points.

@thisjosh A "chain collision" is two chains which merge at some point; afterwards they never separate again, because that's the point of a chain: from any link you can restart the chain computation.

this.josh

Right, they are no isomorphic, that would defeat the nature of the hash.

Thomas Pornin

Oct 26, 2011 21:26

In the attack, you begin with the hash output you want to invert, assume that this output is part of the chains in your table, recompute the chain end, look it up in the table, obtain the chain start, recompute the chain, and hope that it gets you to your attacked output from the other side.

The stored table is a big map of chain-end -> chain-start

this.josh

What does recomputing the chain get you? A hash output comes from exactly one input yes?

Thomas Pornin

In the chain you apply the hash function then the "reduction function", and the latter tends to exhibit collisions.

this.josh

Or is it that you don't know if your inverting function works?

Thomas Pornin

A chain is a succession of invocations of the hash function and the reduction function

the hash function transforms a password into a hash output

the reduction function transforms a hash output into another password

(the reduction function can be any simple mapping you wish, provided that it does not collide "too often")

this.josh

That's crazy!

Thomas Pornin

Oct 26, 2011 21:33

From a given hash output, you can restart a chain, since you only need that to apply the reduction function, then hash, then reduce, then hash, and so on

During table construction, you produced many chains, starting with random passwords.

Each chain led you to a chain end

(for simplicity, assume that the chain end is when you reach a hash output which ends with 12 bits equal to 0 -- one hash output in 4096 on average has that property)

this.josh

like this: password, H(password), R(H(password)), H(R(H(password)))?

Thomas Pornin

yes

now you want to attack a hash output x

and you fervently hope that x is one of the hash outputs you encountered during table construction

i.e. somewhere within the chains, there is a password p (an output of R()) such that H(p) = x

If you can locate that chain, you can recompute it

and recomputing the chain means doing again the H->R->H->R->... thing for that chain

this.josh

So R is just a generator that creates a subset of size k of the range?

Thomas Pornin

and at some point it will produce x as a hash output, and since you are then in the process of rebuilding the chain, you know the input, which is the password you want.

If "passwords" are, for instance, sequences of 6 bytes, you can define R(x) as "the first six bytes of x"

although in a real table you would use "the first six bytes of x, XORed with a given constant"

so that you can have several R() functions

(this is where the table becomes colourful, but be patient)

So, right now, your problem is: assuming that x is part of one of the chains in the table, then:
- how do I identify that chain ?
- how do I get the chain starting point, so that I can recompute it ?

To identify the chain, you recompute the end of the chain, by restarting it at the value x. If x really appeared in a chain somewhere, then, when that chain was computed, the chain-computator obtained x at some point, and kept on from x by applying R then H then R then H... and so on.

this.josh

Ah at some point you will get to the end of one of the chans that has x in it.

Thomas Pornin

Oct 26, 2011 21:42

So you, as an attacker, recompute the chain end until you find a "distinguished hash output", one that marks the end of the chain (it ends with 12 zeros, in my convention)

Once you have the putative chain end, you look it up in the table

the table is a big mapping chain end -> chain start, ordered by chain end

If you do not find your chain end in the table, then failed, too bad.

If you do find it, then the table gives you the chain start s

this.josh

But you won't know an end unless your reduction function drives the output to convergance.

i.e. the 12 zeroes

Thomas Pornin

A chain end is defined as: the output ends with 12 bits

the hash function H is "random"

it will produce such outputs with probability 1/4096

some chains will be longer, some shorter

but you will end up with such a point

(unless you hit a short cycle with no such points, but this is extraordinarily rare so it does not happen in practice -- if in doubt, just add a counter to bail out if you keep walking the chain for more than 1 million of links)

this.josh

Wow, you don't even know the length of the chain! I thought you bound the length with a limit.

Thomas Pornin

You can bound the chain end and that's down in rainbow tables but let's not be hasty

Right now I am talking about Martin/Rivest trade-off

(Rivest is the guy who came up with the idea of the 12 zeros)

(Martin did the rest of the work)

this.josh

Ok, so a random looking hash function creates random length chains, makes sense.

Thomas Pornin

Oct 26, 2011 21:48

So, if I have found the reconstructed chain end in the table, and I got s (the corresponding starting point), then I can rebuild the whole chain

If x is really an hash output part for the chain, then the rebuilding will yield, at some point, a password p (an output of R) which, when given to H as input, yields x

just what, as an attacker, I look for

Now it may happen (and that's often the case) that x is not part of a chain in the table

but simply of another chain which merges with one chain in the table

because a R() invocation in that alternate chain produced the same password than a R() invocation in my stored chain, but with a distinct input

so when I rebuild the whole chain, I reach the chain end without finding x.

Then again, too bad.

This is what happens with ONE table.

Martin then tried to build a big table, and found something important

(pay attention here)

Building the table becomes increasingly difficult when you add chains

because in order to make the table grow, you have to find a new chain which ends with a hash output that the table does not already has

after having reached a relatively small size, prospective new chains happen to merge with one of the already known chains with high probability

so you cannot have a single table which covers a set of passwords of reasonable size ("reasonable" for the attacker: with the table, the attacker successfully breaks exactly the hash outputs which were encountered during table construction, and none other)

Therefore Martin said: let there be several tables

each with its own R() function

hence the definition of R() with an extra XOR with a constant

changing the R() function means changing the whole graph of chains

this.josh

Ouch

Thomas Pornin

so Martin builds a number of tables, and runs the attack for each of them

Building a table has exponential cost with the individual table size

Martin devises an empirical rule (the "Matrix Stopping Rule") which says when keeping on trying to grow a given table is not worth the effort, and beginning a new table would be a better use of CPU

this.josh

And XOR makes disjoint subsets of the password domain?

Thomas Pornin

Not really -- rather, a distinct graph

you may (will) have the same password appear in distinct chains from distinct tables

but the corresponding hash outputs will be processed with distinct R() functions (each table has its own)

so at the next link, the chain diverge again

no merging-until-the-end-of-times between chains which use distinct R() functions

Getting the optimal parameters involves a bit of maths

roughly speaking, to attack a set of N potential passwords, you choose the number of zeros which mark a chain end so that the average chain length is t where t^3 = N

and you will need about t tables

each table will contain about N/t^2 chains

for a storage cost in O(N/t)

CPU cost for the attack is O(t^2) (rebuilding a chain end is O(t), you do that for each of the t tables)

I/O cost is O(t) (for each table, you rebuild one chain end, and do one lookup on the disk)

this.josh

Oct 26, 2011 22:04

But you need diverging compression functions, and I assume these are lossy to drive out information. Thats hard to conceptualize.

Thomas Pornin

so that's why I often describe that as: a table of precomputed hashes (all the hashes in the chains), with a smart compression scheme (you keep only the chain starts and ends, that's enough to rebuild the chain) at the expense of a higher lookup cost (must rebuild the chain ends and do several lookups)

Now let's see the "rainbow" thing

We name the constant in R() its "colour"

just by tradition

Oechslin (I think it was around 2003) thought: why should we have a single colour per table ?

Cannot we make chains where we change colours at each link ?

So we now build chains in the following way:

each chain has length exactly t

there are t colours

The chain building is: p -> H -> R_0 -> H -> R_1 -> H -> R_2 -> ... -> R(t-1) -> H -> chain end

the advantage is then: two chain may totally merge only if they reach the same password with the same colour. Otherwise, they would diverge at the next reduction function.

This allows growing the table much farther

instead of needing about t tables, we just need 1

the disadvantage is that the attack hypothesis is more complex

this.josh

You cant just go down the chain anymore.

Thomas Pornin

instead of thinking "I assume that x is an output of H within my chains", we must make a more precise hypothesis: "I assume that x is an output of H within my chains, followed by R_c for a given colour c"

so I still have to rebuild t chain ends, one for each colour hypothesis

the advantage of the rainbow table over the Martin/Rivest scheme is hidden deep within the detailed computations

basically, attack CPU cost is halved

and, as another advantage, since chain length is no longer "average" but fixed to t for all chains, it is somewhat easier to distribute the chain end rebuilding to several nodes in a parallel architecture (say, a GPU)

this.josh

Wow, that is an impressive improvement.

Thomas Pornin

Then Biham, Shamir and a few others came and said: Martin/Rivest and Oechslin tables are two special case of a generic scheme

in which you have "several" tables (but less than t) and each table uses several colours (but not one colour per link)

@thisjosh Note that in practice, the bottleneck is not CPU cost, it is I/O

a modern hard disk will do about 100 random accesses per second, no more

rainbow tables do not offer a big advantage for I/O

Shamir & co defined "thick rainbow tables", "thin rainbow tables", "fuzzy rainbow tables"... which are variants depending on how you decide to switch colours within a chain

None is generically better or worse than the other, but it gives a lot of configurable parameters to optimize for a given architecture

The salient things to remember:

- A rainbow table of any sort will successfully find p such that H(p) = x if and only if x was encountered during table construction (in a chain which was ultimately kept, i.e. not a chain which merged with an already known chain).

- Building a rainbow table for a set of N passwords has cost about 1.72*N

(1.72 is e-1; the 0.72 are the extra chains which were computed but discarded because they collided with already known chains; the decision to stop at 1.72 comes from the empirical Matrix Stopping Rule. You can go further but it is exponentially expensive.)

- The whole thing works only because chain building is deterministic, and is identical during the table building and during the attack. Which is why salts kill rainbow tables: with a salt, the attack does not use the same H() than the one used for building the table.

- There is nothing magical here. Just probabilities.

There, course is over. I must go back to battling with Word.

this.josh

Oct 26, 2011 22:24

Thank you Thomas.

Ninefingers

Oct 26, 2011 22:45

I feel like I missed out on some fun

Conversation ended Oct 26, 2011 at 22:45.

Thomas Pornin does his crypto thing.

Oct '1126

The DMZ

A serious place where infosec is discussed PS we don't do hard...

context of the conversation
join this room
about this room

Participants

Thomas Pornin 81%
this.josh 17%
Jeff Ferland 0%
Ninefingers 0%

all times are UTC

site design / logo © 2025 Stack Exchange Inc; legal

mobile