Welcome Guest [Log In] [Register]
Welcome to Crypto. We hope you enjoy your visit.


You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.


Join our community!


If you're already a member please log in to your account to access all of our features:

Username:   Password:
Add Reply
Can you break Crystalline?
Topic Started: May 13 2015, 01:28 PM (713 Views)
mmcc
Just registered
[ * ]
I've released a new cipher called Crystalline and I would like people to examine it for weaknesses.

All comments, questions and opinions are very welcome.

You can download the source, plus Windows binares, from here:

https://crystalline.codeplex.com/
Offline Profile Quote Post Goto Top
 
Karl-Uwe Frank
NSA worthy
[ *  *  *  *  *  * ]
After a short glimpse on the source code of Crystalline it becomes obvious that the algorithm has a certain weakness origin from the usage of a key file which is muliplicated with a salt file generating 32bit integer values that are used as offset points into the plaintext to define where to swap bits and bytes.

The core function for generating a "keystream" is called shift(). This shift() function does a sequential walk through the key and salt file foward and backwards. I had the impression that this caluclation of the "keystream" have to produce massive repeating pattern. Although the results of ENT and diehard posted by the author don't show any significant unusual results.

Any acceptable PRNG and of course any keystream of a cipher should pass ENT, diehard, tests for bistatisitc, for bias and the maurer test.

Quit imporant though is the more intense test suite TestU01 with the Aphabit and Rabbit test as well as smallcrush, crush and bigcrush and finally the book stack test.

These tests seperate the wheat from the chaff.


I have just tested a 10MB file filled with all "0x00" that I encrypted with Crystalline.

The resulting file "zero_10MB.bin.enc" was then tested with ENT, test for bitstatistic, bias, maurer-test and Alphabit, Rabbit from Testu01.

The results are devastating, even when ENT, bistatitstic and maurer-test don't report any problem.

Test for bias however reveal that my expectation was right, the cipher algorithm produce repeating pattern.

Also Alphabit and Rabbit show massive problems of the cipher algorithm in generating a uniform distribution.

It is obvious that it will not survive smallcush, not to mention crush, bigcrush and the book stack test.

Testing the same 10MB file encrypted with RC4 does not show any problem on all tests.



All test files and sources (apart from TestU01) can be downloaded here http://www.freecx.co.uk/cryptanalysis/Crystalline/


TESTU01-123 over here https://www.iro.umontreal.ca/~simardr/testu01/tu01.html




Code:
 
The[space]result[space]from[space]the[space]bias[space]test[space]using[space]1[space]bytes-per-block


10485760[space]samples
bit[space][space][space]0:[space].5-0.008334[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]53.9737)
bit[space][space][space]1:[space].5+0.002210[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]-14.3099)
bit[space][space][space]3:[space].5+0.000943[space]almost[space]certainly[space]non-uniform[space](>99.9%)
bit[space][space][space]4:[space].5-0.006623[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]42.8902)
bit[space][space][space]5:[space].5-0.007347[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]47.5836)
bit[space][space][space]6:[space].5-0.001432[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]9.2756)
bit[space][space][space]7:[space].5+0.001754[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]-11.3613)
Overall[space]Chi[space]Squared[space]value[space]is[space]7474.808[space](threshold[space]18.4753)
Overall[space]likely[space]non-uniform[space](>99%)



Code:
 
The[space]result[space]from[space]the[space]bias[space]test[space]using[space]4[space]bytes-per-block


2621440[space]samples
bit[space][space][space]0:[space].5-0.005303[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]17.1714)
bit[space][space][space]2:[space].5-0.001210[space]likely[space]non-uniform[space](>99%)
bit[space][space][space]3:[space].5+0.004385[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]-14.1981)
bit[space][space][space]4:[space].5-0.004168[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]13.4965)
bit[space][space][space]5:[space].5-0.016636[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]53.8711)
bit[space][space][space]6:[space].5-0.003848[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]12.4614)
bit[space][space][space]7:[space].5+0.003569[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]-11.5571)
bit[space][space][space]8:[space].5-0.008936[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]28.9361)
bit[space][space][space]9:[space].5-0.007000[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]22.6683)
bit[space][space]10:[space].5-0.004647[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]15.0492)
bit[space][space]11:[space].5-0.001280[space]almost[space]certainly[space]non-uniform[space](>99.9%)
bit[space][space]12:[space].5-0.003558[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]11.5225)
bit[space][space]13:[space].5-0.007427[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]24.0494)
bit[space][space]14:[space].5+0.005453[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]-17.6569)
bit[space][space]15:[space].5+0.007569[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]-24.5089)
bit[space][space]16:[space].5-0.011592[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]37.5372)
bit[space][space]17:[space].5+0.019047[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]-61.6768)
bit[space][space]18:[space].5+0.009125[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]-29.5475)
bit[space][space]19:[space].5-0.004335[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]14.0388)
bit[space][space]20:[space].5-0.008176[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]26.4742)
bit[space][space]21:[space].5-0.000980[space]likely[space]non-uniform[space](>99%)
bit[space][space]22:[space].5-0.014989[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]48.5373)
bit[space][space]23:[space].5+0.004902[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]-15.8732)
bit[space][space]24:[space].5-0.007505[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]24.3026)
bit[space][space]25:[space].5-0.003479[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]11.2668)
bit[space][space]26:[space].5-0.002761[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]8.93961)
bit[space][space]27:[space].5+0.005004[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]-16.203)
bit[space][space]28:[space].5-0.010588[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]34.2872)
bit[space][space]29:[space].5-0.004346[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]14.0746)
bit[space][space]30:[space].5+0.007656[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]-24.7905)
bit[space][space]31:[space].5-0.009023[space]certainly[space]non-uniform[space](>6sigma,[space]z[space]=[space]29.2165)
Overall[space]Chi[space]Squared[space]value[space]is[space]20607.94[space](threshold[space]52.1914)
Overall[space]likely[space]non-uniform[space](>99%)


Code:
 
The[space]result[space]from[space]the[space]Alphabit/Rabbit[space]test


==============================================
10485760[space]byte[space]for[space]testing


========[space]Running[space]Rabbit[space]Test[space]=========

=========[space]Summary[space]results[space]of[space]Rabbit[space]=========

[space]Version:[space][space][space][space][space][space][space][space][space][space]TestU01[space]1.2.3
[space]File:[space][space][space][space][space][space][space][space][space][space][space][space][space]zero_10MB.bin.enc
[space]Number[space]of[space]bits:[space][space][space]10485760
[space]Number[space]of[space]statistics:[space][space]39
[space]Total[space]CPU[space]time:[space][space][space]00:00:07.67
[space]The[space]following[space]tests[space]gave[space]p-values[space]outside[space][0.001,[space]0.9990]:
[space](eps[space][space]means[space]a[space]value[space]<[space]1.0e-300):
[space](eps1[space]means[space]a[space]value[space]<[space]1.0e-15):

[space][space][space][space][space][space][space]Test[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]p-value
[space]----------------------------------------------
[space][space]1[space][space]MultinomialBitsOver[space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space][space]2[space][space]ClosePairsBitMatch,[space]t[space]=[space]2[space][space][space][space][space][space]2.9e-68
[space][space]3[space][space]ClosePairsBitMatch,[space]t[space]=[space]4[space][space][space][space][space]1.6e-146
[space][space]4[space][space]AppearanceSpacings[space][space][space][space][space][space][space][space][space][space][space][space][space][space]1.9e-8
[space][space]6[space][space]LempelZiv[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]1[space]-[space]eps1
[space][space]7[space][space]Fourier1[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]1[space]-[space]eps1
[space][space]8[space][space]Fourier3[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space][space]9[space][space]LongestHeadRun[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space]10[space][space]PeriodsInStrings[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space]11[space][space]HammingWeight[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space]12[space][space]HammingCorr,[space]L[space]=[space]32[space][space][space][space][space][space][space][space][space][space][space][space]2.0e-14
[space]13[space][space]HammingCorr,[space]L[space]=[space]64[space][space][space][space][space][space][space][space][space][space][space][space][space]7.2e-5
[space]14[space][space]HammingCorr,[space]L[space]=[space]128[space][space][space][space][space][space][space][space][space][space][space]1[space]-[space]1.4e-11
[space]15[space][space]HammingIndep,[space]L[space]=[space]16[space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space]16[space][space]HammingIndep,[space]L[space]=[space]32[space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space]17[space][space]HammingIndep,[space]L[space]=[space]64[space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space]18[space][space]AutoCor[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]1[space]-[space][space]6.4e-9
[space]19[space][space]AutoCor[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]1[space]-[space]eps1
[space]20[space][space]Run[space]of[space]bits[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space]20[space][space]Run[space]of[space]bits[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]1.0e-4
[space]21[space][space]MatrixRank,[space]32[space]x[space]32[space][space][space][space][space][space][space][space][space][space][space][space]3.3e-16
[space]24[space][space]RandomWalk1[space]H[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space]24[space][space]RandomWalk1[space]M[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space]24[space][space]RandomWalk1[space]J[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space]24[space][space]RandomWalk1[space]R[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space]24[space][space]RandomWalk1[space]C[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space]25[space][space]RandomWalk1[space]H[space](L[space]=[space]1024)[space][space][space][space][space][space][space][space][space]eps[space][space]
[space]25[space][space]RandomWalk1[space]M[space](L[space]=[space]1024)[space][space][space][space][space][space][space][space][space]eps[space][space]
[space]25[space][space]RandomWalk1[space]J[space](L[space]=[space]1024)[space][space][space][space][space][space][space][space][space]eps[space][space]
[space]25[space][space]RandomWalk1[space]R[space](L[space]=[space]1024)[space][space][space][space][space][space][space][space][space]eps[space][space]
[space]25[space][space]RandomWalk1[space]C[space](L[space]=[space]1024)[space][space][space][space][space][space][space][space][space]eps[space][space]
[space]26[space][space]RandomWalk1[space]H[space](L[space]=[space]10016)[space][space][space][space][space][space][space][space]eps[space][space]
[space]26[space][space]RandomWalk1[space]M[space](L[space]=[space]10016)[space][space][space][space][space][space][space][space]eps[space][space]
[space]26[space][space]RandomWalk1[space]J[space](L[space]=[space]10016)[space][space][space][space][space][space][space][space]eps[space][space]
[space]26[space][space]RandomWalk1[space]C[space](L[space]=[space]10016)[space][space][space][space][space][space][space]2.1e-5
[space]----------------------------------------------
[space]All[space]other[space]tests[space]were[space]passed





*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*




========[space]Running[space]Alphabit[space]Test[space]========

=========[space]Summary[space]results[space]of[space]Alphabit[space]=========

[space]Version:[space][space][space][space][space][space][space][space][space][space]TestU01[space]1.2.3
[space]File:[space][space][space][space][space][space][space][space][space][space][space][space][space]zero_10MB.bin.enc
[space]Number[space]of[space]bits:[space][space][space]10485760
[space]Number[space]of[space]statistics:[space][space]17
[space]Total[space]CPU[space]time:[space][space][space]00:00:00.43
[space]The[space]following[space]tests[space]gave[space]p-values[space]outside[space][0.001,[space]0.9990]:
[space](eps[space][space]means[space]a[space]value[space]<[space]1.0e-300):
[space](eps1[space]means[space]a[space]value[space]<[space]1.0e-15):

[space][space][space][space][space][space][space]Test[space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space][space]p-value
[space]----------------------------------------------
[space][space]1[space][space]MultinomialBitsOver,[space]L[space]=[space]2[space][space][space][space][space][space][space]eps[space][space]
[space][space]2[space][space]MultinomialBitsOver,[space]L[space]=[space]4[space][space][space][space][space][space][space]eps[space][space]
[space][space]3[space][space]MultinomialBitsOver,[space]L[space]=[space]8[space][space][space][space][space][space][space]eps[space][space]
[space][space]4[space][space]MultinomialBitsOver,[space]L[space]=[space]16[space][space][space][space][space][space]eps[space][space]
[space][space]5[space][space]HammingIndep,[space]L[space]=[space]16[space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space][space]6[space][space]HammingIndep,[space]L[space]=[space]32[space][space][space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space][space]7[space][space]HammingCorr,[space]L[space]=[space]32[space][space][space][space][space][space][space][space][space][space][space][space]2.0e-14
[space][space]8[space][space]RandomWalk1[space]H[space](L[space]=[space]64)[space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space][space]8[space][space]RandomWalk1[space]M[space](L[space]=[space]64)[space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space][space]8[space][space]RandomWalk1[space]J[space](L[space]=[space]64)[space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space][space]8[space][space]RandomWalk1[space]R[space](L[space]=[space]64)[space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space][space]8[space][space]RandomWalk1[space]C[space](L[space]=[space]64)[space][space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space][space]9[space][space]RandomWalk1[space]H[space](L[space]=[space]320)[space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space][space]9[space][space]RandomWalk1[space]M[space](L[space]=[space]320)[space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space][space]9[space][space]RandomWalk1[space]J[space](L[space]=[space]320)[space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space][space]9[space][space]RandomWalk1[space]R[space](L[space]=[space]320)[space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space][space]9[space][space]RandomWalk1[space]C[space](L[space]=[space]320)[space][space][space][space][space][space][space][space][space][space]eps[space][space]
[space]----------------------------------------------


Some remarks on usability of the propose cipher:

Every communication partner would need a TRNG (True Random Number Generator) in order to build the pre-shared key file and the separate salt file having the same size as the key file.

A new salt file has to be generated for every message encrypted. This salt must be send alogside the message in order to allow the receiver decrypting the ciphertext.

The problem with sending the salt file is, that any adversary will now have access to the half key because the salt is used in a simple multiplication in the function shift(). This will offer any sophisticated attacker a great chance in finding the key.



cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua
zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k
G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
Offline Profile Quote Post Goto Top
 
mmcc
Just registered
[ * ]
The important part, as I mentioned before on Devshed, is whether this is leaking information about the key/salt/plaintext. So far, the answer to that appears to be no. Any TRNG uses upper and lower bounds to maintain frequency counts for any potential output value. This function will emerge as a general oscillation over time and will become the dominant signal in the ciphertext. This is a good thing.
Offline Profile Quote Post Goto Top
 
Karl-Uwe Frank
NSA worthy
[ *  *  *  *  *  * ]
Knowledge of the salt (half the key) give an adversary enough information to figure out the key. Also repeating pattern in the keystream generation function is where to look for and your algorithm produce them massively. I suppose that just some-one with good mathematical skills can find the key having the salt. Perhaps you should publish your algorithm at sci.crypt to get some reply from more skilled cryptanalyst's.


The start of the discussion on devshed.com
http://forums.devshed.com/security-cryptography-17/crystalline-cipher-testers-required-969138.html
cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua
zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k
G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
Offline Profile Quote Post Goto Top
 
Karl-Uwe Frank
NSA worthy
[ *  *  *  *  *  * ]
EDIT: I removed the list of offset values because there are only 65536 possible offset values calculating each byte of the key with each byte of the salt.
Edited by Karl-Uwe Frank, May 17 2015, 09:40 AM.
cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua
zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k
G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
Offline Profile Quote Post Goto Top
 
mmcc
Just registered
[ * ]
Karl-Uwe Frank
May 16 2015, 04:46 PM
Knowledge of the salt (half the key) give an adversary enough information to figure out the key. Also repeating pattern in the keystream generation function is where to look for and your algorithm produce them massively. I suppose that just some-one with good mathematical skills can find the key having the salt. Perhaps you should publish your algorithm at sci.crypt to get some reply from more skilled cryptanalyst's.


The start of the discussion on devshed.com
http://forums.devshed.com/security-cryptography-17/crystalline-cipher-testers-required-969138.html
In a classical cipher, I would agree. The problem with this in Crystalline is that given a ciphertext, there is no reference point from which to begin such analysis. The binary is scrambled and its position is dependent on the position of bits and bytes from previous rounds of scrambling. So, even with the salt the number of permutations to restore each byte and bit is unbelievable and there is no way to verify that the correct choices have been made until they have worked back through every round.

Offhand, I don't think a solar system full of high end super computers would make much of a dent using that approach.

Anyway, I thought I would leave a message here about the RStudio Project file that I will be using during the analysis. Follow the link for further info:

http://forums.devshed.com/security-cryptography/969138-crystalline-cipher-testers-required-post2956486.html#post2956486
Offline Profile Quote Post Goto Top
 
Karl-Uwe Frank
NSA worthy
[ *  *  *  *  *  * ]
It seem the author was trying to implement a cipher algorithm proposed by Ueli Maurer in 1992

Conditionally-Perfect Secrecy and a Provably-Secure Randomized Cipher
Author: Ueli M. Maurer


http://saluc.engr.uconn.edu/refs/stream_cipher/maurer92randomized.pdf
Edited by Karl-Uwe Frank, May 10 2016, 08:19 PM.
cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua
zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k
G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
DealsFor.me - The best sales, coupons, and discounts for you
« Previous Topic · Challenges · Next Topic »
Add Reply