3DS 2-Time Pad Challenge

Here's some basic info on neimod's two-time pad challenge for the 3DS. Ask in #3dsdev on EFNet if you want more information.

 <neimod> anyone up for a 3ds two-time pad challenge?
 <mtheall> ?
 <Brian117> uh
 <Brian117> will there be snacks?
 <neimod> if you bring some
 <Brian117> will there be air conditioning?
 <neimod> each update of the 3ds firmware is encrypted with the same xor stream, which is a security flaw known as the two-time pad (or multiple-time pad)
 <neimod> the challenge is... given the different updated versions of the encrypted 3ds firmware, try to decrypt the firmware
 <Brian117> i forfeit
 <neimod> if you're serious about trying, i can provide some sample files
 <X-Scale> I could try it, neimod
 <X-Scale> So...the 1st sample will be F1 ^ P, the 2nd F2 ^ P, etc ?
 <neimod> yes correct
 <X-Scale> I see...any idea how long is that pad ?
 <neimod> practically infinitely long
 <X-Scale> hmm
 <gruetzkop> aw
 <gruetzkop> so is in sample n there is a section that is 0 in clear text, we can decrypt that section in every other sample
 <crediar> aren't updates in encrypted containers?
 <neimod> there are a couple sections which are filled with zeros, but that's maybe 0.1% of the entire file
 <neimod> crediar: that is all stripped away
 * psyduck_ is now known as psyduckg
 * You are no longer marked as being away
 <gruetzkop> isnt enc_a ^ enc_b == a ^ b
 <neimod> yes
 <neimod> it gives the xor of plaintexts
 <crediar> nintendo already made that mistake with the GC IPL
 <gruetzkop> yeah
 <crediar> neimod what do I need to help you?
 <neimod> well how would you solve the challenge?
 * You have been marked as being away
 * Yuuki has quit ()
 * Yuuki (Yuuki@dslb-178-000-064-224.pools.arcor-ip.net) has joined #3dsdev
 <crediar> first I would just xor the files and look at the output
 <crediar> just gimme the files and I will give it a try
 <mtheall> evidently the classical solution is to perform crib dragging. if i find time later maybe i will request to participate
 * sepp256 (~sepp256@picasso.ee.psu.edu) has joined #3dsdev
 * sepp256_ has quit (Read error: Operation timed out)
 <neimod> crib dragging works best with actual word-based text, it's not quite that easy when dealing with pure binary files
 <mtheall> there's bound to be blocks of text somewhere
 <X-Scale> neimod: how can you be sure the same pad is used in all of those firmware files ?
 <neimod> if it wasn't, you would not be able to read any strings of text from it by xoring
 <neimod> it is the same pad, it is a fact
 <mtheall> what does the ability of text being read by xoring have to do with it using the same xor pad?
 <neimod> if it were different pads, the result would be complete gibberish
 <mtheall> are you implying that you already have a non-gibberish result?
 <neimod> very small parts
 <mtheall> okay then now i believe it
 <neimod> if you want to try
 <neimod> generate an xorpad, and xor it with 10 low entropic data files, eg arm code
 <neimod> then try to guess the xorpad
 <mtheall> does figuring out one xor value in the stream give you the rest of the xor pad for a given block?
 <neimod> no
 <neimod> not directly
 <neimod> you could think of the files being similar, and shifted around
 <neimod> the kernel is not rewritten from scratch for each update i would imagine
 <crediar> arm asm just pokes right into your eyes
 <mtheall> so there's not a really good way to get the rest of the xor pad for a block when you figure out part of it
 <neimod> pointers would probably change each update
 <mtheall> other than randomly guessing or a genetic algorithm maybe
 <neimod> there are many options to try
 <mtheall> but at least the xor at one position is identical across all streams
 <neimod> the ideal goal is to find an exploit in a small piece of revealed code, that would allow pwning of the arm9
 <neimod> like a buffer overflow or similar
 <crediar> is the 3ds little or big endian?
 <mtheall> i need to get my eyes on more arm code
 <mtheall> i'm assuming little endian
 <neimod> little endian
 <costis> leedle endian
 <neimod> lets say you know that file 2 is shifted 200 bytes forward relative to file 1
 <neimod> and lets say you know the xorpad for block 5
 <neimod> so, you know the plain text for file 1 for block 5, and since file 2 is shifted relative to file 1, you then also know that this plaintext is the the plain text of file 2 shifted 200 bytes forward
 <neimod> and so, you know the xorpad of block 5, shifted 200 bytes forward
 <neimod> now repeat the same process, and you can expand your xorpad
 <mtheall> at least until you get to a part where there's a shift *and* a change. but i guess having more than two streams helps mitigate that
 * syslock has quit (Quit: tschüß...)
 <Brian117> my head just exploded
 <mtheall> that can't be good
 * GeekShad1 is now known as GeekShado
 <neimod> the key part is figuring out if a file has shifted (so the bytes are exactly the same), and by how many bytes
 * lameboy2 (~lameboyad@122.150.47.211) has joined #3dsdev
 <neimod> obviously this doesn't apply for the entire file, but for smaller blocks it probably does
 <costis> someone write some code
 <mtheall> you could xor file1^(file2 shifted x bytes)^file1 and maybe get some chunks
 <costis> to do automated analysis
 * lameboy has quit (Ping timeout: 306 seconds)
 * lameboy2 is now known as lameboy
 <mtheall> errrr
 <neimod> that would be file2 shifted x bytes
 <mtheall> file1^(file2 shifted) and look for chunks of 0s
 <mtheall> nvm. i should not do xor math while driving
 * You are no longer marked as being away
 <mtheall> file1^(file2 shifted)^file2
 <neimod> you cannot shift files yourself, because then the xorpads would differ, resulting in gibberish
 <mtheall> that's true
 <mtheall> i have to shift *after* xor and compare
 <mtheall> (file1^pad)^((file2^pad) shifted) and look for chunks of 0s
 <mtheall> that's my last guess
 * You have been marked as being away
 * You are no longer marked as being away
 <Brian117> wrong
 * You have been marked as being away
 <paraz0an> you're typing on IRC while driving?
 <mtheall> paraz0an: i was at the time
 * zeromus has quit (Read error: Operation timed out)
 * zeromus (~poople@cpe-66-69-203-119.austin.res.rr.com) has joined #3dsdev
 * h4PPYC4T (~h4PPYC4T@p5DDF52F7.dip.t-dialin.net) has joined #3dsdev
 * pXd has quit (Ping timeout: 245 seconds)
 * Yuuki has quit ()
 * Luigi__ has quit (Read error: Operation timed out)
 * lameboy has quit (Read error: Connection reset by peer)
 * lameboy (~lameboyad@122.150.47.211) has joined #3dsdev
 * neimod has quit (Ping timeout: 630 seconds)
 <phoenix_> eh, 3ds has an arm9?
 <zeromus> well its got to, as part of the nds core
 <phoenix_> dont see why that couldnt be pretty accurately emulated/handled with the arm11's
 * ld16 (~jeff@pool-74-104-172-30.bstnma.fios.verizon.net) has joined #3dsdev
 <zeromus> there are little difference between the arm versions