1:05AM here and I can fully agree with and approve of that statement.

3:21 AM, best time for that tbh.

05:03AM I think I won

@@gaydolfhitler6310 depending on if it's pre- or post-sleep

2:17 am

Of course I know 3Blue1Brown's videos. They are blowing my mind every time. I wish I could have explained this topic as well as 3Blue1Brown would have done it. But I'm happy it was good enough for you to understand it :)

clever

Unfortunately she exists in a GF(2) vector space.

She is independent

that's awesome!

me neither!

"Field" ist im deutschen ein Körper. Vermutlich solltest du hier aufhören zu lesen, mir war langweilig. Eine sog. algebraische Struktur, d.h. grob gesagt eine Menge, "mit der man Rechnen kann". (es gibt eine Addition, Multiplikation und die üblichen Rechenregeln: Assoziativität, Kommutativität, Distributivität. Außerdem gibt es jeweils ein "neutrales Element" [für "+" ist das 0, für "*" ist das 1] und inverse Elemente [also zu 3 zb. -3 bzw 1/3]). Im Endeffekt kann man also mit einem Körper rechnen "wie mit den reellen oder den rationalen Zahlen". Das ist auch nicht wirklich "magisch". Beim Lösen von Gleichungen braucht man eigentlich nur diese Eigenschaften, welche Zahlen man dann zur Verfügung hat, ist prinzipiell egal: Beispiel: x^2 - 1 = 0 (x + 1)(x-1) = 0 x = 1 oder x = -1 Damit hat diese Gleichung über den rationalen Zahlen zwei Lösungen, nämlich 1 und -1. Nun ist aber "-1" das additive Inverse zu 1, d.h. die Zahl aus dem Körper, die man zu 1 addieren muss, damit 0 heraus kommt. Über GF(2) ist 1 + 1 = 0. 1 ist also selbstinvers, d.h. -1 = 1. Über GF(2) hat diese Gleichung also nur eine Lösung, nämlich 1 (man könnte auch -1 schreiben, so ähnlich wie man statt 1/2 ja auch 2/4 schreiben könnte über den rationalen Zahlen) Man beachte, dass etwas die dritte binomische Formel, die hier verwendet wurde, über jedem Körper funktioniert, denn: Sind a, b Elemente aus einem beliebigen Körper, so ist (a-b)(a+b) = (Distributivität) a(a+b) - b(a+b) = (Distributivität) a*a + a*b - b*a - b*b = (Kommutativität) a^2 + a*b - a*b - b^2 = (-a*b ist das additive Inverse zu a*b) a^2 + 0 - b^2 = a^2 - b^2

I am thinking about a reason why this sould not work... And I can't find any... can someone pls confirm (or deny) that this is working?

If I recall the updater code correctly, the hash was checked after the zip was extracted to a temporary directory, but before the pre-copy was executed. Including the original pre-copy and two copies of a modified version wouldn't have worked: either the final pre-copy on the filesystem is your modified version (in which case the hash would fail) or it's the original (in which case you haven't hacked the router).

This is a novel way to force a hash collision in this computation. In general, a hash collision is when two different inputs have the same hash. SHA256 is specifically designed to make this extremely unlikely. But in this case, the final hash isn't a SHA256 hash, it's a lot of SHA256 hashes XORed together. So, XOR is being used as a secondary hash function, and it's much easier to cause collisions with that. The clever part is how they were able to control the SHA256 hashes to create a desired input to the XOR function, without having to brute force arbitrary SHA256 hashes (which is practically impossible).

Great question, if you suppose that each vector has the same chance of appearing I got 28,8788...% aswell. I wonder if picking the n first integers as in the video produces some uniform distribution on the SHA-256 hash though, I have absolutely no idea. If someone good in crypto knows, I'd like to know more :)

how did yo get that result?

Ohh.. I thought in the wrong direction. With linear independence I thought it was about orthogonality and multiplication to zero. Not linear combination. That makes more sense!

a) the python code is complete. What do you mean with "forge the hash"? b) XOR is equivalent to plus in GF(2). So you just have to do your calculations in that finite-field (I know it's untypical for your everyday calculator, but in sage you can see that we set the matrix to `Zmod(2)`

A) If I remember my crypto class correctly, We have two hashes, the valid hash of the payload and our invalid hash after our modifications. We are looking to add some content in addition to our modifications (the backdoored pre_copy script) that when xor'd with the new invalid hash outputs the previously valid hash. B) Under GF(2) addition = subtraction = xor. The way I was taught was to take the vector as a polynomial. Every place where you have a set bit, you have a variable of a chosen power. For example, 1011 = x^3 + x + 1 and 0101 = x^2 + 1. If I "add" these two polynomials together under GF(2) (or "xor" the bit values) I get 1110 = x^3 + x^2 + x^1! Because coefficients of a series of polynomials can be represented as entries in a matrix, we can use something like sage to transform the matrix into reduced row-echelon form, solving the series of equations and showing us which of the linearly independent "vectors" / polynomials need to be "added" to our changes to produce the valid hash.

a) oh yeah ok. as you can see in the video, I just modified the original software_updater code to spit out that hash.

Solving a system of equations basically only relies upon having certain operations available to you (besides the usual rules that Associativity and Commutativity), namely elements have inverse elements. If you have that, you can basically just solve equations like you always would. Example: Consider the equation x^2 - 1 = 0 (x - 1)(x+1) = 0 If this equation was to be solved over the rational numbers, its solutions would be 1 and -1. Over GF(2) however, "-1", i.e. "the additive inverse to 1" or the number that when added to 1 results in 0, is 1, because 1 + 1 = 0 ==> 1 = -1 That means over GF(2) this equation has only one solution: 1 (or -1, it doesnt really matter which one you state as the solution, since they are the same. Much like 1/2 = 2/4 over the rationals).

You should have probably at least mentioned what a field is, and why its useful in this case, that ({0, 1}, XOR, *) is in fact a field. Then again, I also understand why you chose not to...

It isn't with Cramer rule and a finite field of dim 2

Any *two* non-equal vectors are LI in GF(2)^n but you could have three non-equal vectors that are not. e.g. (0,1), (1,1) and (1,0) in GF(2)^2. The problem here is to get 256 LI vectors in GF(2)^256.

You can have linearly dependent vectors without a collision. For example: (1 0 0 0 0 ...) (0 1 0 0 0 ...) (1 1 0 0 0 ...) The third vector can be reached by adding the first two, hence they are linearly dependent. That said, "randomly" chosen vectors are likely to be independent in general (unless you choose more vectors than the dimension, then they are guaranteed to be dependent).

Necroing a comment from 1 year ago, lol. Yes, but 3 (or more) vectors in gf 2 can be linearly dependant and all unique at the same time. For example, (0001), (0010) and (0011) are all different and linearly dependant. : )

Flo S He might talk about it on his site but he's definitely talked about it in the hardware video where he borrowed a chip whisperer.

He is comparing all the vectors in the matrix against each others

Yup, I'm dumb! XD Didn't see he created a matrix with old vectors! Thanks!

it's on the 34c3ctf site: archive.aachen.ccc.de/34c3ctf.ccc.ac/challenges/

almightyhydra don't use something easily modeled like a single xor, if for example the operation to concat hashes was another sha256 instead of xor, this wouldn't have worked

Don't XOR for crypto.

Have you looked at any crypto algorithm? I think all of them use XOR at some point ;)

Exactly, the safest crypto would use only MOV and maybe a JMP at the end. :D

movinator proves that mov is no more safe than anything else because everything could potentially be reduced to a series of movs

It’s GF(2) ;) it’s a very different world

LiveOverflow tbh I expected 1+1=10 >.

But you have only one bit. 10 would require two bits. But do you see how this results ends in a 0? Basically you can imagine that only this 0 stays, because you don’t have space for the 1

LiveOverflow yea think you explained that really well in the video and it does make sense I just didn't expect that ^^

Hritik Vijay and how would you get sha256 to return the unit vectors?

He would have to create files that have their hashes [1,0,0...0], [0,1,0...] which is not possible. He had to work with the hashes of the files he just created. Because he can't just send hashes, he has to send files whose hashes xored get the desired result.

Oops! My bad.

Axel Latvala ?