# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
MTGAP
Daedalian Member

 Posted: Fri Mar 06, 2009 3:32 am    Post subject: 1 Preface: I know that RC4 is no longer considered secure. But I found the biggest break ever. Please tell me why I am wrong. From Wikipedia: "In the event that part or all of its state has been revealed (or guessed correctly), it should be impossible to reconstruct the stream of random numbers prior to the revelation." However, this is clearly not the case with RC4. Here is the number generation algorithm (in C, but it works pretty much the same way in any language). i and j are the iterators and S is the 256-byte array. i = (i + 1) % 256; j = (j + S[i]) % 256; swap(S[i], S[j]); return S[(S[i] + S[j]) % 256]; Given the values of i and j, we can easily determine the previous value of i by subtracting one. And we can easily find the value of j by subtracting S[i]. So it is trivial to "reconstruct the stream of random numbers prior to the revalation." P.S. What are some secure and relatively simple CSPRNGs? All I've found are the eStream ciphers, but there's not many very good resources on them and some of them are weird._________________This statement is false.
Antrax
ESL Student

 Posted: Fri Mar 06, 2009 7:24 am    Post subject: 2 Good stream ciphers are a bit tricky. RC4 is still very commonly used despite its glaring weaknesses. Either RC5 or RC6 are improvements over it (the other is a block cipher, I never remember which is which). Eli Biham has his own stream cipher, which is probably safe, called Py. Adi Shamir once showed a pretty impressive cipher, but I have no clue how he named it and a quick google doesn't reveal it, so I guess it was flawed. What is also often used is a good block cipher. To encrypt the stream you encode the block number under some (static) key, and XOR with the plaintext. Given standard assumptions, this "stream" cipher is as strong as the block cipher. The price is computations, which is also why RC4 is still so popular. As for your first question, I'm not very knowledgeable about stream ciphers, but it seems the permutation S is also a part of the state. In fact, that's the "key". The other problem is that even given an S at some point in time, S is updated with every cycle, so it's not necessarily true that you can compute S[i] in time t-1, even given S and i in time t._________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
MTGAP
Daedalian Member

Posted: Fri Mar 06, 2009 2:30 pm    Post subject: 3

 Antrax wrote: As for your first question, I'm not very knowledgeable about stream ciphers, but it seems the permutation S is also a part of the state. In fact, that's the "key". The other problem is that even given an S at some point in time, S is updated with every cycle, so it's not necessarily true that you can compute S[i] in time t-1, even given S and i in time t.

So you're saying that it is secure because it takes as long/longer to calculate in reverse than it does to calculate it forward? So in the time it takes to calculate, S has changed, changing the result?
_________________
This statement is false.
Antrax
ESL Student

 Posted: Fri Mar 06, 2009 3:08 pm    Post subject: 4 No, I'm saying that in time t+1, what used to be S[i] in time t (that you want to calculate) is now S[j], and j is what you're trying to find out._________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
raekuul
Lives under a bridge & tells stories.

Posted: Fri Mar 06, 2009 4:11 pm    Post subject: 5

 Quote: So you're saying that it is secure because it takes as long/longer to calculate in reverse than it does to calculate it forward? So in the time it takes to calculate, S has changed, changing the result?
Schroedinger called - he wants his cat back.
MTGAP
Daedalian Member

Posted: Fri Mar 06, 2009 5:10 pm    Post subject: 6

raekuul wrote:
 Quote: So you're saying that it is secure because it takes as long/longer to calculate in reverse than it does to calculate it forward? So in the time it takes to calculate, S has changed, changing the result?
Schroedinger called - he wants his cat back.

That's not exactly what I meant. Plus, Schroedinger's cat and the Heisenberg Uncertainty Principle are not the same thing. HUP deals with the inability to observe something, because observing it changes it*. The cat deals with quantum mechanics, where something can be both true and false.

*which is not what I'm saying. I'm saying that by the time the previous number is calculated, the generator will have changed the values, since it continuously changes them.

Edit: He wants his cat back, huh? He already has it. And doesn't have it. At the same time. (Now that is Schroedinger's cat.)

Edit 2: Your joke was still funny.
_________________
This statement is false.
raekuul
Lives under a bridge & tells stories.

Posted: Sat Mar 07, 2009 3:19 pm    Post subject: 7

 MTGAP wrote: That's not exactly what I meant. Plus, Schroedinger's cat and the Heisenberg Uncertainty Principle are not the same thing. HUP deals with the inability to observe something, because observing it changes it*. The cat deals with quantum mechanics, where something can be both true and false. *which is not what I'm saying. I'm saying that by the time the previous number is calculated, the generator will have changed the values, since it continuously changes them. ... Edit 2: Your joke was still funny.

Point taken, but Rule of Funny overrides Rule of Actuality when I try to make jokes.
worm
unregistered

Posted: Sat Mar 07, 2009 5:32 pm    Post subject: 8

 MTGAP wrote: Plus, Schroedinger's cat and the Heisenberg Uncertainty Principle are not the same thing. HUP deals with the inability to observe something, because observing it changes it*. The cat deals with quantum mechanics, where something can be both true and false. :

Aside...

They are different, but Schrodinger's cat is very much about the observer effect and they both deal with quantum mechanics.

Schrodinger's cat tries to connect probabilities of wavefunctions on the atomic level (i.e. a particle that may or may not decay) to the macroworld (whether the cat is alive or dead). When the system is observed, the wavefunction of the particle collapses and only one of the probable outcomes is observed.

The Heisenberg uncertainty principle is a different observer effect, but "inability to observe something, because observing it changes it" is a bit misleading. The properties the principle deals with can, in fact, be measured. The uncertainty comes with the particle/wave duality that comes with moving near the speed of light. You can measure a wave property or you can measure a particle property, but you can't accurately measure both at the same time.
Dented Ford
Hoopy Frood

Posted: Sat Mar 07, 2009 9:47 pm    Post subject: 9

 worm wrote: Schrodinger's cat tries to connect probabilities of wavefunctions on the atomic level
Schrodinger's cat is a cat, and therefore was never in the box in the first place, it just disappeared, and turned up later, washing itself as if nothing was the matter when you discovered it. On the other hand, real quantum is me finding a lottery ticket from the 3rd January draw. So for a couple of months, I've been both a multi-millionaire and as poor as a churchmouse at the same time. It was only the act of checking the ticket today that collapsed the wavefunctions and proved that I'm still a churchmouse.
worm
unregistered

 Posted: Sun Mar 08, 2009 3:48 am    Post subject: 10 just don't go into any wormholes looking for the alternate universe where you're a multi-millionaire. I really wish they'd change the name already. Btw, if you could successfully get the cat in the box, it's not simultaneously dead and alive until an observer opens the box. The cat is the only observer necessary.
raekuul
Lives under a bridge & tells stories.

 Posted: Sun Mar 08, 2009 3:54 am    Post subject: 11 We really should get back to talking about encryption/decryption. The Schroedinger's Cat thing was supposed to be a throwaway joke.
MTGAP
Daedalian Member

Posted: Mon Mar 09, 2009 2:54 am    Post subject: 12

 raekuul wrote: We really should get back to talking about encryption/decryption. The Schroedinger's Cat thing was supposed to be a throwaway joke.

Okay.

After seeing that study by Biham and Shamir (which one? XD) I decided to do a frequency analysis of RC4 for each output byte. Biham and Shamir found that the second output was more likely to be a zero than it should have been. So I decided to do a frequency analysis of the second output, by seeding it, and then generating two outputs, and taking the second one. I generated one million second outputs. Since there are 256 possible results, the number of occurrences for each number 0 to 255 should be around 3000 to 4500. This was the case for most numbers, but for others, there were ZERO occurrences in a million trials. What's the deal with that?

Just to be extra thorough, I did a test where I generated ten million outputs. Here is the result. The first number is the number outputted, and the second number is the number of occurrences. (Counting numbers can get confusing. Some numbers represent objects, while others represent cardinalities. )

 Code: 0: 159948 1: 55334 2: 84541 3: 0 4: 0 5: 58638 6: 124509 7: 0 8: 0 9: 54624 10: 0 11: 0 12: 37090 13: 125843 14: 0 15: 87383 16: 113669 17: 40691 18: 0 19: 111615 20: 7539 21: 51767 22: 0 23: 131131 24: 52803 25: 23964 26: 66077 27: 40934 28: 0 29: 0 30: 5585 31: 0 32: 0 33: 0 34: 9549 35: 52675 36: 84033 37: 102662 38: 0 39: 95335 40: 0 41: 130342 42: 78414 43: 5849 44: 37513 45: 0 46: 28773 47: 12455 48: 0 49: 0 50: 50423 51: 36213 52: 39694 53: 0 54: 0 55: 78390 56: 0 57: 96775 58: 0 59: 27423 60: 40605 61: 0 62: 39590 63: 19264 64: 10415 65: 38459 66: 0 67: 161234 68: 170370 69: 43261 70: 53931 71: 0 72: 0 73: 0 74: 0 75: 45484 76: 127280 77: 0 78: 40337 79: 45652 80: 23492 81: 90525 82: 49014 83: 61747 84: 43862 85: 137810 86: 86081 87: 39436 88: 66760 89: 16735 90: 85473 91: 8527 92: 54709 93: 54080 94: 50216 95: 44042 96: 88057 97: 84466 98: 139230 99: 41145 100: 120159 101: 0 102: 68674 103: 0 104: 0 105: 0 106: 48677 107: 0 108: 52444 109: 27689 110: 0 111: 0 112: 0 113: 39837 114: 27177 115: 6962 116: 52607 117: 0 118: 8598 119: 0 120: 83451 121: 5140 122: 163004 123: 87394 124: 82809 125: 59127 126: 0 127: 0 128: 0 129: 0 130: 84913 131: 91584 132: 45624 133: 0 134: 0 135: 4830 136: 0 137: 0 138: 53573 139: 0 140: 65257 141: 104814 142: 0 143: 16830 144: 130329 145: 26718 146: 37361 147: 0 148: 14954 149: 0 150: 48901 151: 36326 152: 5389 153: 0 154: 0 155: 0 156: 0 157: 35819 158: 0 159: 105763 160: 0 161: 0 162: 101445 163: 86573 164: 155498 165: 43847 166: 0 167: 0 168: 0 169: 31305 170: 26057 171: 18915 172: 0 173: 145770 174: 69808 175: 106467 176: 76902 177: 13691 178: 0 179: 4766 180: 85970 181: 80007 182: 0 183: 0 184: 26297 185: 5129 186: 119186 187: 0 188: 10780 189: 40626 190: 17838 191: 31941 192: 0 193: 0 194: 64033 195: 48358 196: 0 197: 76773 198: 0 199: 14377 200: 135160 201: 5515 202: 82551 203: 0 204: 51555 205: 0 206: 99133 207: 82460 208: 31920 209: 71101 210: 48540 211: 45105 212: 0 213: 9052 214: 52226 215: 83664 216: 89315 217: 0 218: 0 219: 158673 220: 27313 221: 0 222: 8033 223: 5028 224: 70196 225: 36448 226: 4479 227: 40862 228: 0 229: 75826 230: 10104 231: 0 232: 57133 233: 27290 234: 0 235: 55697 236: 0 237: 0 238: 0 239: 0 240: 47442 241: 25096 242: 0 243: 133974 244: 128294 245: 0 246: 6603 247: 46297 248: 0 249: 121512 250: 0 251: 28258 252: 0 253: 0 254: 88183 255: 63377

Can anyone explain this unusual output, or is it a bug in my program? Now that I think about it, it's probably a bug. Those darn bugs.
_________________
This statement is false.
Antrax
ESL Student

 Posted: Mon Mar 09, 2009 7:01 am    Post subject: 13 It should be pretty easy to get an implemented RC4 cipher, so you'll know it's bug-free. It's not impossible under some ill-chosen key you'll get stuck in a loop shorter than the maximum possible length (within the permutation) and then you'll get zero occurrences of some numbers. If you're REALLY interested, I can call up someone I've known back in college, he's doing a PhD under Biham and I think he dealt a lot with RC4._________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
MTGAP
Daedalian Member

Posted: Mon Mar 09, 2009 12:25 pm    Post subject: 14

 Antrax wrote: It should be pretty easy to get an implemented RC4 cipher, so you'll know it's bug-free. It's not impossible under some ill-chosen key you'll get stuck in a loop shorter than the maximum possible length (within the permutation) and then you'll get zero occurrences of some numbers. If you're REALLY interested, I can call up someone I've known back in college, he's doing a PhD under Biham and I think he dealt a lot with RC4.

That can't be the problem though, because I'm not running it continuously. When I do that, the distribution works fine. I'm looking at the occurrences for the second output, each time with a different key. This probably means that some different keys result in the same string of output.

I want to take a class with Biham.
_________________
This statement is false.
Antrax
ESL Student

 Posted: Mon Mar 09, 2009 12:31 pm    Post subject: 15 I think you can still late-register to winter semester at the Technion, then._________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
MTGAP
Daedalian Member

Posted: Mon Mar 09, 2009 1:10 pm    Post subject: 16

 Antrax wrote: I think you can still late-register to winter semester at the Technion, then.

Maybe if I was five years older and lived in Israel.
_________________
This statement is false.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersAntraxDented FordMTGAPraekuulworm Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum