# 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.

Post a reply
Username
Message body

 Emoticons View more Emoticons
 [quote="MTGAP"][quote="raekuul"]We really should get back to talking about encryption/decryption. The Schroedinger's Cat thing was supposed to be a throwaway joke.[/quote] 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 [/code] 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.[/quote]
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 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
 Topic review
Author Message
MTGAP
Posted: Mon Mar 09, 2009 1:10 pm    Post subject: 1

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.
Antrax
Posted: Mon Mar 09, 2009 12:31 pm    Post subject: 0

I think you can still late-register to winter semester at the Technion, then.
MTGAP
Posted: Mon Mar 09, 2009 12:25 pm    Post subject: -1

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.
Antrax
Posted: Mon Mar 09, 2009 7:01 am    Post subject: -2

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.
MTGAP
Posted: Mon Mar 09, 2009 2:54 am    Post subject: -3

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.
raekuul
Posted: Sun Mar 08, 2009 3:54 am    Post subject: -4

We really should get back to talking about encryption/decryption. The Schroedinger's Cat thing was supposed to be a throwaway joke.
worm
Posted: Sun Mar 08, 2009 3:48 am    Post subject: -5

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.
Dented Ford
Posted: Sat Mar 07, 2009 9:47 pm    Post subject: -6

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
Posted: Sat Mar 07, 2009 5:32 pm    Post subject: -7

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.
raekuul
Posted: Sat Mar 07, 2009 3:19 pm    Post subject: -8

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.
MTGAP
Posted: Fri Mar 06, 2009 5:10 pm    Post subject: -9

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.
raekuul
Posted: Fri Mar 06, 2009 4:11 pm    Post subject: -10

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.
Antrax
Posted: Fri Mar 06, 2009 3:08 pm    Post subject: -11

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.
MTGAP
Posted: Fri Mar 06, 2009 2:30 pm    Post subject: -12

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?
Antrax
Posted: Fri Mar 06, 2009 7:24 am    Post subject: -13

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.
MTGAP
Posted: Fri Mar 06, 2009 3:32 am    Post subject: -14

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.

Powered by phpBB © 2001, 2005 phpBB Group
Site Design by Wx3