492506 - naive groebner basis preimage attack on md5

Status: VERIFIED INVALID

(Core :: Security, defect)

Description

[georgi - hopefully not receiving bugspam]

naive groebner basis preimage attack on md5

spent some time on this, resolve as you wish.

i tried algebraic preimage attack on md5 - working in $GF(2)[x0 .. x_i]$ and using groebner basis with arguments that avoid crashes (LOL).

to my surprise i got unexpected correct *partial* results that pass the insanity check.

example of what the proggie finds.
the final states of md5 with unrolled loops are:
a = XX(I, a, b, c, d, inp[ 8], S41, 0x6FA87E4F) # 57 <-- this is step
number
d = XX(I, d, a, b, c, inp[15], S42, 0xFE2CE6E0) # 58
c = XX(I, c, d, a, b, inp[ 6], S43, 0xA3014314) # 59
b = XX(I, b, c, d, a, inp[13], S44, 0x4E0811A1) # 60
a = XX(I, a, b, c, d, inp[ 4], S41, 0xF7537E82) # 61
d = XX(I, d, a, b, c, inp[11], S42, 0xBD3AF235) # 62
c = XX(I, c, d, a, b, inp[ 2], S43, 0x2AD7D2BB) # 63
b = XX(I, b, c, d, a, inp[ 9], S44, 0xEB86D391) # 64

the proggie calls a ``state'' the value of the tuple:
(step,whichoperand,whichoperation,bit)
['resbit' means the return of XX()]

given only a md5 hash and unknown input, in 38 minutes and 1G ram the proggie correctly finds states:
'57_resbit_resbit_0=0', '57_resbit_resbit_6=0', '57_resbit_resbit_8=1',  '58_resbit_resbit_12=0', '58_resbit_resbit_13=1', '58_resbit_resbit_19=0', '58_resbit_resbit_21=0', '58_resbit_resbit_22=0', '58_resbit_resbit_29=0', '58_resbit_resbit_30=0', '58_resbit_resbit_31=0', '58_resbit_resbit_7=1'
i.e. 3 bits of the result of step 57 and 9 bits of the results of step 58 (it finds other stuff too and continues running).

about the implementation:
md5 uses bitwise operations + addition modulo 32 and they can be
implemented in $GF(2)[x0 .. x_i]$

so i start with symbolic input [x0 .. x_127] and work with the md5
implementation in $GF(2)[x0 ... x_i]$. every state of the algorithm is polynomial of the input.

drama is with 128 variables, expressions are quite complicated and do
not fit in current VM.

so i use a trick - when an expressions $E$ is ``too big'' i introduce
new variable $x_i$, add equation $ x_i = E $ and return the new var $
x_i $. $i = i+1$

this makes the final system at least well defined (numequations <= numvars).

attached is a sage program.

Comment 1

[georgi - hopefully not receiving bugspam]

Attachment: mds5.sage (GPL3+ licenced source code.this is *buggy*. use next or supported version)

Comment 2

[Dave Townsend [:mossop]]

How is this a Firefox bug?

Comment 3

[georgi - hopefully not receiving bugspam]

> How is this a Firefox bug?

i don't claim it is a firefox bug.

but if the proggie finds a result, md5 should be dropped.

feel free to resolve as invalid.

i am interested in the discussion of the ppl watching me on b.m.o.

Comment 4

[Dave Townsend [:mossop]]

This would probably be better done as a newsgroup posting to the crypto newsgroup I think. As it is I'm moving this out of the Firefox product as it doesn't belong there.

Comment 5

[georgi - hopefully not receiving bugspam]

is there a mailing list hosted on .mozilla to which to post ?

Comment 6

[Reed Loden [:reed]]

(In reply to comment #5)
> is there a mailing list hosted on .mozilla to which to post ?

mozilla.dev.tech.crypto
[e-mail]

Comment 7

[georgi - hopefully not receiving bugspam]

thanks, posted it.

Comment 8

[georgi - hopefully not receiving bugspam]

Attachment: GPL3 mds5.sage

Comment 9

[timeless]

Comment on attachment 376919 [details]
GPL3 mds5.sage

george: posting GPL3 content to a bug tracker where people work on code that is not hindered by GPL3 makes me feel very uncomfortable, could you please *not* do that?

Comment 10

[georgi - hopefully not receiving bugspam]

timeless: stay assured that this won't hit your codebase.

if you insist in putting it in the codebase, i will relicense it.

Comment 11

[timeless]

the problem is that NSS developers who *work* on this codebase from this bug tracker might be tainted by reading an attachment to their bug tracker.

Comment 12

[georgi - hopefully not receiving bugspam]

so will GPL2+ contaminate the nss developers ?

Comment 13

[georgi - hopefully not receiving bugspam]

GPL3 mds5.sage:

http://www.guninski.com/mds5.sage

Comment 14

[georgi - hopefully not receiving bugspam]

sorry if the GPL3+ caused you troubles - i believe the bugzilla admins can fix it at most with SQL

Comment 15

[Daniel Veditz [:dveditz]]

Comment on attachment 376876 [details]
mds5.sage (GPL3+ licenced source code.this is *buggy*. use next or supported version)

As long as it's clearly labeled there shouldn't be a problem -- people can easily avoid opening attachments.

Comment 16

[Daniel Veditz [:dveditz]]

(In reply to comment #12)
> so will GPL2+ contaminate the nss developers ?

For the things lawyers worry about, yes. Mozilla code, including NSS, is licensed under "MPL or GPL". It is valid for someone to take it and combine with GPL code, but that requires taking the Mozilla part as GPL-only. This is fine for someone else to do, but our policy requires keeping our hosted Mozilla code licensed under both so we cannot accept code tainted by pure-GPL code.

Lawyers worry that developers who have merely looked at GPL code and later happen to write code similar to that code could be sued for violating the GPL. Therefore if your work requires you to write MPL-licensed crypto code you cannot afford to even glance at crypto code under an incompatible or non-free license for fear of being later sued. At least if you work for a company that does business in a country as lawsuit-happy as the US and some other western countries.

Comment 17

[Daniel Veditz [:dveditz]]

Resolving bug, discussion moved to .crypto list/newsgroup. If the goal is "md5 should be dropped" (comment 3) we have other bugs on that (including patches).

Comment 18

[georgi - hopefully not receiving bugspam]

> If the goal is "md5 should be dropped" (comment 3)

that was the point. 
the program was just an ugly piece of warez demonstrating some partial results in md5, it was never ment for production or constructive code.

dveditz, your writing about the GPL makes me think the usa is in really bad times, anyway thanks for the info...

Comment 19

[Bartłomiej Brzozowiec (BartZilla)]

(In reply to comment #16)
> (...)
> Lawyers worry that developers who have merely looked at GPL code and later
> happen to write code similar to that code could be sued for violating the GPL.
> (...)

Could you provide at least one example of such case, please (ie. someone (FSF?) sued someone else because of merely looking into GPL-only code)? If not, I think this explanation is a pure BS.
Mozilla hates GPL because it wouldn't allow them to do things like "Firefox Repacks" (ie. mixing Firefox with closed-source, proprietary software and distribute it; see eg. https://wiki.mozilla.org/Talk:Releases/Fx_3.0.7_Partners).

BTW - I also added GPL-only attachment (in bug 454792)...

Comment 20

[Reed Loden [:reed]]

The problem is GPLv3, not GPL. Read all comments in the bug before ranting, please.

Comment 21

[Bartłomiej Brzozowiec (BartZilla)]

(In reply to comment #20)
> The problem is GPLv3, not GPL. Read all comments in the bug before ranting,
> please.

Your comment doesn't make sense. There are not much differences between GPLv2 and GPLv3 (and BTW - Mozilla Trilicense includes GPL v2 "or later", so it includes also GPLv3).

If you claim that "the problem is GPLv3, not GPL", please substantiate it somehow rather than attacking me personally by suggesting that I didn't read all relevant comments.

Comment 22

[Daniel Veditz [:dveditz]]

(In reply to comment #19)
> (In reply to comment #16)
> > Lawyers worry that developers who have merely looked at GPL code and later
> > happen to write code similar to that code could be sued for violating the GPL.
> 
> Could you provide at least one example of such case, please (ie. someone (FSF?)
> sued someone else because of merely looking into GPL-only code)? If not, I
> think this explanation is a pure BS.

I don't know of any _suits_, but I know several instances of lawyers worrying about such suits and enforcing rules on developers. For a long time, perhaps still, Microsoft employees were forbidden from even downloading Mozilla source. That's not "GPL" per se, but the same kind of license contamination fear. Every company I've worked at other than MoCo has had such lawyers. And the valley here has seen suits about whether some code was _really_ a clean-room reimplementation or reverse-engineered copying. Again, not GPL, totally proprietary code in fact, but the lawyers aren't dreaming up worries completely out of thin air.

> Mozilla hates GPL

I'm sure that would be news to the people who worked very very hard (particularly Gerv) to relicense our entire codebase so that GPL'd projects could use our code. That might be news to the authors of the GPL'd addons we happily host at AMO.

Incidentally, the person who raise the concern in comment 9 (timeless) doesn't work for Mozilla or on Firefox, and probably likes the GPL just fine in his personal life. But his day job is for one of those companies with lawyers who worry about intellectual property rights. (A European one, as it happens, so it's not just America georgi should worry about in comment 18.)

> because it wouldn't allow them to do things like "Firefox
> Repacks" (ie. mixing Firefox with closed-source, proprietary software and

You say "proprietary" like it's a bad word. It's a choice, and Mozilla is all about choice. You can choose to compile a pure GPL Iceweasel of your very own and my Mom can choose to have a handy proprietary addon that helps with bargain hunting on eBay. Everyone wins!

Comment 23

[georgi - hopefully not receiving bugspam]

>If the goal is "md5 should be dropped" (comment 3) we have other bugs on that (including patches).

are these bugs public?

if you drop md5 you probably will want to drop md4 too - it is more linear, less rounds.

an interesting question is what *to keep*

Comment 24

[Gervase Markham [:gerv]]

> Lawyers worry that developers who have merely looked at GPL code and later
> happen to write code similar to that code could be sued for violating the GPL.

This is possible, in the "anything is possible" sense. I think it's rubbish - copyright law is about copying, not about ideas - but I accept that some people are nevertheless concerned.

However, it's worth noting that the concerned developers could only be sued by the copyright holder of the code. So timeless need only be worried about opening that file if he thinks that, later in his life, Georgi is going to sue him for writing code which looks a bit like it. Maybe timeless doesn't trust georgi, I don't know. But this scenario does seem to be to be a bit less likely than being struck by lightning.

"I can't look at any GPLed code" (or GPLv3ed code) is an irrational position. "I can't look at any GPLed code whose copyright is held by litigious people" might be a more defensible one. But only if you also refused to look at code under any other license, free or proprietary, which was written by those self-same litigious people. In other words, fear the copyright holder (or not), not the licence.

On the other hand, I think that everyone would appreciate it if people attaching files to Bugzilla were to make them available under the standard Mozilla licensing terms. It's just so much less hassle. Thank you :-)

Gerv

Comment 25

[Grey Hodge (jX)]

> "I can't look at any GPLed code" (or GPLv3ed code) is an irrational position.

It's a perfectly defensible position if it's the policy of one's employer, which is far more likely (sadly).

Comment 26

[Gervase Markham [:gerv]]

Grey Hodge: it is possible for the position to be both irrational and that of one's employer at the same time :-)

Such a position normally comes from the false idea that if some GPLed code accidentally makes its way into their proprietary code, they can be forced to open source the entire application. That's entirely false. 

If the employer stops you looking at code whose copyright is held by anyone else, then that would be a defensible (if ultra-paranoid) position on their part. But claiming that having engineers looking at GPLed code is somehow more dangerous to their business than having them looking at proprietary code owned by e.g. Microsoft is simply untrue.

Gerv

Comment 27

[georgi - hopefully not receiving bugspam]

does this mean if i mass spam @lists with code *ending* with GPL3 license i can sue almost all the world? ;)

Comment 28

[georgi - hopefully not receiving bugspam]

Attachment: mds5.sage - licence GPL2 OR (inclusive OR) GPL3+

trying to quit the GPL flame in this bug - GPL2 or GPL3