The DMZ

Scott Pack

00:06

I'm not sure about their drama program here. I can't recall seeing any of their shows. My theatre work was all at Morehead State.

this.josh

Oh, my mistake.

Scott Pack

That's right it is!

We do have a pretty good journalism school, but how that prestige and money filters its way through the college, I don't know.

Rory Alsop

09:26

@thisjosh Shakespeare is still pretty popular in schools in Scotland. Probably because of 'the Scottish play'

admittedly I think about 50% of his stuff was dross, some was excellent - Hamlet, Romeo&Juliet, Macbeth

didn't like any of them as plays though, just to read

Iszi

12:41

@RoryAlsop Right... because lego.stackexchange.com would have made too much sense...

Scott Pack

But now they can use it for both legos and minecraft!

Iszi

BTW: I still hold the opinion that users not in the private beta should still have read permissions to the private beta site - just not allowed to vote or post comments/questions/answers.

Scott Pack

I agree

Rory Alsop

@Iszi ahh - lego was explicitly prohibited, by the Lego Group themselves :-)

Iszi

@RoryAlsop Owwie

Rory Alsop

12:50

@ScottPack and it is for lego, well, at least 99 per cent

there is a knex question in there

Scott Pack

What about duplo?

Rory Alsop

yep - it is lego

@Iszi I think that makes sense - have you asked that in meta.so?

Iszi

@RoryAlsop I get the feeling that if I dig deep enough, I'll find it's already been said and shot down. Maybe later, when I have the time.

M'vy

13:07

Hi there

Rory Alsop

afternoon @Mvy

Stack Exchange

Scott Pack

14:52

@GrahamLee I see that Oxford is/was a JAMF customer. Did you ever deal with it?

Ninefingers

15:51

Guys - question. Does anyone think editing qotw questions like this:

24

Q: Why does WMI Provider Host (WmiPrvSE.exe) keep spiking my CPU?

I generally keep my laptop on 24x7, and at the end of the day it's really annoying to have my thighs burnt because over overheating. The overheating seems to be a result of WMI Provider Host (WmiPrvSE.exe) spiking the CPU utilization to 25% every few minutes. Why does this happen? I have an H...

Is a good idea for qotw posts?

If so, I'll do it

Graham Lee

@ScottPack no. I was in the physics department, not computer services

(Oxford is even more federated than you might expect)

Rory Alsop

@Ninefingers I think it is an excellent idea. More than happy for you to edit them (won't take long :-)

Thomas Pornin

Dammit, @AviD got two new badges on Monday

Rory Alsop

@ThomasPornin is that bad?

Thomas Pornin

@RoryAlsop He now has 84 badges, and I have only 82 "nice answers"

Rory Alsop

16:06

@ThomasPornin Hahaha. interesting distribution - he has more silvers than me, but less golds and bronzes. I think that means he has better answers

@ThomasPornin so you need 2 more nice answers to keep score, right?

Ninefingers

Y'know, not to pimp my own answer, but:

25

Q: What are rainbow tables and how are they used?

Where can I find one? Is there a pot of gold at the end? How do I protect against them? From the Area51 proposal This question was IT Security Question of the Week. Read the Sep 09, 2011 blog entry for more details or submit your own Question of the Week.

attack-prevention cryptography attacks hash

1

A: How can rainbow tables be used for a dictionary attack?

Finding a decent explanation of rainbow tables was something I struggled with, so firstly I'll cover what they are. I will get to your question in the end. My sources for this are this guide and the wikipedia article. Why can't I just use a big bucket of hashes? Firstly the naive way to build a...

Thomas Pornin

@RoryAlsop I do not want to keep score, I want to win. So 3 more nice answers.

Rory Alsop

@ThomasPornin LOL

@Ninefingers Woah. That just slips beyond my maths level into "ooo, look at the cool symbols"

I mean, I understand the concept, I think, but woah!

Ninefingers

@RoryAlsop I had a lot of fun writing it. I knew I'd seen it before and looking through past qotws, there it was!

Thomas Pornin

In a rainbow table, the "rainbow" part is a technicality. It has a practical importance, but not by a huge factor (about 2 when compared with classical Hellman / Rivest trade-off)

The black-and-white tables are easier to explain, I think

Rory Alsop

16:15

time to commute - later all

Ninefingers

Tada, all qotw questions now have banners

3

Thomas Pornin

@Ninefingers Nifty.

Ninefingers

@ThomasPornin I got the excavator badge for it too.

Thomas Pornin

@Ninefingers The archaeologist badge will be harder.

Ninefingers

@ThomasPornin I know I know... for us low-reps these badges are hard to get. I'm still hoping one day something will come along that I can write an insane answer for on SO and get me a Great Answer badge and I swear the reversal badge is impossible to get...

Jeff Ferland

16:30

@Ninefingers Nice!

Thomas Pornin

17:10

@Ninefingers For reversal, there must be a thoroughly bad question which gets awfully downvoted, and yet which does not get closed.

Our current moderators are way too much law&order-oriented to allow such a thing to happen.

There are only two open questions with score of -5 or less in sec.SE.

Possibly, @D.W. may achieve at some point the reversal badge (he already has 11 of the needed 20 upvotes)

Not that DW says all that can be said on the subject.

Ninefingers

17:27

@ThomasPornin I think I remember you providing an X11 answer somewhere too.

Thomas Pornin

@Ninefingers Yes, but it was about Wayland (as a candidate for X11 replacement)

8

Q: Passive and active attacks via X11. Is Wayland any better?

In The Linux Security Circus: On GUI isolation - The Invisible Things Lab's blog, Joanna Rutkowska describes attacks from one X11 app on another and the general problem of the lack of GUI-level isolation, and how it essentially nullifies all the desktop security. One application can sniff or ...

desktop x11

Thomas Pornin

17:46

Given that I am now supposed to transfer 6 pages of specification, carefully typeset with LaTeX, into a Word document, I may have enough incentive to really write a thorough "security issues in X11" answer.

Scott Pack

yum install tex2word -y

Thomas Pornin

It's not that easy: I must incorporate the text with the same fonts and typographic conventions than the rest of the document, and I must do so under supervision of Word's "revision control" feature.

I guess it's gonna be copy&paste time.

Stack Exchange

19:11

Stack Overflow Blog: SE Podcast #24

Posted by Alex Miller on October 26th, 2011

Jeff & Joel are joined this week by Eric Ries, author and expert on The Lean Startup. Topics for the chat include:

Jeff Atwood is joining the podcast from his vacation. He has an announcement! He is having twins! In February! This will bring the total Atwood Child Count to 3, meaning they will outnumber the adults. Congratulations, Jeff!

Talk of children leads to talk of war which leads to talk of Battlefield 3. The core team spent some time playing today. It incentivizes working as a team!

ANYWAY. Eric Ries is our guest today! He’s got a new book out called The Lean Startup. What is a …

Rory Alsop

19:52

@Ninefingers yay!

this.josh

20:57

@Ninefingers Nice answer!

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

21:13

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

@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

21:25

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

Thomas Pornin

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

21:33

That's crazy!

Thomas Pornin

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

21:42

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

Thomas Pornin

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

21:47

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

Thomas Pornin

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

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

22:24

Thank you Thomas.

Ninefingers

22:45

I feel like I missed out on some fun

Ninefingers

22:55

@thisjosh As Thomas has said, no. For completeness, here's some maths background. A ring is a structure of things that fit a a specific set of axioms. These are:

AC: commutative addition a+b = b+a

AA: associative addition a+(b+c) = (a+b)+c

AN: A+0 = 0+A (neutral element)

this.josh

Multiplicative identity

Ninefingers

AI: A+(-A)=(-A)+A=0 (Inverses)

Not for rings

this.josh

What?

Ninefingers

multiplicative associativity and distributivity

secure.wikimedia.org/wikibooks/en/wiki/Abstract_Algebra/…

You might be thinking of groups

Or fields

this.josh

Doesn't it go set, field, ring, group?

Ninefingers

23:00

Not really

this.josh

Oh oops, rings only have addative identity.

Ninefingers

because you can define a set that is neither a field, ring or group

But generally the sets you start from encompass fields, rings and groups

this.josh

right a set is the most basic it has the least restrictions

Ninefingers

That's close enough - a set is just a container - I can define a set X = {q : q=2p+7 = 3 mod 11, p \in N}

this.josh

a group is a set with one operator

a ring has two operators with the axioms you sepcified

Ninefingers

23:03

a group has axioms too

so does a field

rings, fields and groups have axioms

sets are just collections of whatever you want them to be

a ring, field or group is therefore also a set

this.josh

yes addative commutativity

err addative assocativity

Ninefingers

the way to think of it is this - a set is any collection of elements (polynomials, elliptic curves, plain old numbers) that you want

That particular set may or may not be a group ring or field

if the right axioms hold then it can be one of those

to test it, you'd try to see if the axioms work

Iszi

this.josh

Nice graphic Iszi!

Ninefingers

knowing that the axioms work and that the structure is a group is kinda like programming to an interface - you know that any structure satisfying that set of axioms behaves in a specific way

so for example if something is a group you know every element in it has an inverse and that there is an identity

Iszi

23:09

@thisjosh Friend of mine sent it via StumbleUpon.

Ninefingers

@Iszi Our sysadmin I think would appreciate that :)

this.josh

In a cluster I think you don't know which machine is serving the resources, just one of the cluster

Ninefingers

@thisjosh If you're interested I have this book on abstract algebra. It's a great read (well, if you're after a crime thriller, maybe not, but a maths textbook):

amazon.co.uk/Rings-Fields-Groups-Introduction-Mathematics/dp/…

this.josh

I'll take a look. I have a couple books on my shelf, but I never seem to get past abelian groups.

Ninefingers

@thisjosh this one starts with rings and fields (literally, it covers them in the same order as in the title) and the first few chapters introduce and play with a set of axioms

then he changes course and goes into rings. I like it because you get used to the ideas first, then start worrying about rings and fields and what they are etc.

this.josh

23:20

Thanks @ninefingers. It is a touch expensive, maybe I can find a library copy.

I prefer paying small library fines to buying expensive books.

Ninefingers

@thisjosh yeah, I borrowed it at first, liked it and brought it. I think it's worth it, but there are other books other people no doubt prefer. Best to try first.

this.josh

Hah I just realized the irony of asking Josh for clarification on his question.

0

Q: Decent programmer looking to learn to Hack

I'm a decent programmer, fluent in several languages. Python, Ruby, JavaScript, Haskell, and Scheme are my favorites. I'm currently adding Perl to the mix. I haven't done much "low-level" programming. I've screwed around at the logic gate level and built a few basic chips, but I've never progra...

penetration-test

Transcript for