Anyone else here do cryptanalysis?

[beansbaxter]

I'm trying to predict the next X bytes of a stream for which I already have a roughly 7500 byte-long sample. The range of values in the stream is a known fixed count.

On sample intervals of 96 bytes or so I can see trends:

Only 55-65% of the posible byte values are used
5-10% of those bytes repeat up to 4 times in the 96-byte sequence
if I sum a fixed count of the bytes the sum is always in a range of 65-220 witht he average falling between 157 and 162
the same byte never appears more than once in the same grouping if I stick to the groupings given out by this black box - length of grouping is known fixed.
the unicity distance between bytes averages between 7 and 8
pairs of bytes repeat frequently, as do some sets of triples
4 and 5-byte groups do not repeat often at all
there has never been a repeat grouping over 5 bytes long

frequency distributions show that over time, the freq. of each given byte falls along the bell curve. This also applies to the frequency of the frequencies and the freq. of the unicity distance over a fixed sample length.

Total problem set size per sample is approximately 17.7 billion combinations
I think I've manged to narrow the problem set down to 750,000 combinations, but currently that doesn't mean anything.

Anyone know how to hack a bell curve?

 

[CycloWizard]

Originally posted by: beansbaxter
if I sum a fixed count of the bytes the sum is always in a range of 65-220 witht he average falling between 157 and 162

the same byte never appears more than once in the same grouping if I stick to the groupings given out by this black box - length of grouping is known fixed.

frequency distributions show that over time, the freq. of each given byte falls along the bell curve. This also applies to the frequency of the frequencies and the freq. of the unicity distance over a fixed sample length.

Anyone know how to hack a bell curve?

A 'bell curve' distribution is typically a gaussian distribution, which is very well-defined mathematically (link). Since you know that the mean falls between 157 and 162, you know the standard deviation and the true mean. Simply just stick the results of all your runs together and find the true mean, then measure the standard deviation and you'll have the entire probability function defined. This defines your 'black box' in terms of the likelihood of it spitting out a given byte.

Once the probability function is defined based on all your previous runs, you can use it to predict future bytes. I believe that whatever byte closest to the mean that has not yet been produced is most likely the next byte. There is no guarantee that it will be this byte, but it has a higher probability than the others. Alternatively, you could add in a random component to your prediction algorithm. The best approach depends on what you're trying to do, and I'm not a programmer, so I'm not going to be much help on that end of things.

 

[beansbaxter]

if you're right about this and I completely crack this thing then I owe you a huge favor. I've been trying random number generation filtered thru some behavioral rules I came up with. This turned out to be more precise than a brute force attack, but not as accurate. The generation attacks gave me a smaller set of candidate sequences, but the results sucked. If I do a brute-force attack based on chosen ciphertext, I CAN predict the next sequence, but it's one of 17500 sequences (WAY better than 17.7 billion) returned by the program. I'm convinced if I refine my methods of selecting ciphertext bytes for the BF I'll nail this thing. Thanks for your help.

 

[SagaLore]

That sounds fun... I understand encryption, but I'm not skilled enough in math to break it myself.

 

[beansbaxter]

I really need some more help with this. I have been working on this forever making some breakthroughs but having limited success.

I should be able to eventually solve this by simply using recurrence analysis, but does anyone have a list of steps I can and should go through to take a more mathematical approach to this?

Thanks in advance.

 

[FelixDeCat]

I dont. It seems too complicated, and for good reason, it is!

 

[dkozloski]

Are you trying to rob a bank or break Las Vegas?

 

[beansbaxter]

This is actually something I am working on for work. If I can get this done, it will save a lot of time and I can automate more things.

 

[Caligynemania]

Sounds like the encryption youre using is pretty shoddy. Some simple differential cryptanalysis (which it seems you've done) will probably lead you to pretty good results. If you have access to mid-steps for your black box, use a boomerang attack to figure out the formula even further.

 

[beansbaxter]

Originally posted by: Caligynemania
Sounds like the encryption youre using is pretty shoddy. Some simple differential cryptanalysis (which it seems you've done) will probably lead you to pretty good results. If you have access to mid-steps for your black box, use a boomerang attack to figure out the formula even further.

Can you tell me more about a boomerang attack, please??