|
Can you break Crystalline?
|
|
Topic Started: May 13 2015, 01:28 PM (713 Views)
|
|
mmcc
|
May 13 2015, 01:28 PM
Post #1
|
- Posts:
- 3
- Group:
- Members
- Member
- #4,267
- Joined:
- May 12, 2015
|
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/
|
|
|
| |
|
Karl-Uwe Frank
|
May 15 2015, 04:03 PM
Post #2
|
- Posts:
- 639
- Group:
- Members
- Member
- #3,502
- Joined:
- July 11, 2011
|
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=
|
| |
|
mmcc
|
May 16 2015, 04:30 PM
Post #3
|
- Posts:
- 3
- Group:
- Members
- Member
- #4,267
- Joined:
- May 12, 2015
|
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.
|
|
|
| |
|
Karl-Uwe Frank
|
May 16 2015, 04:46 PM
Post #4
|
- Posts:
- 639
- Group:
- Members
- Member
- #3,502
- Joined:
- July 11, 2011
|
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=
|
| |
|
Karl-Uwe Frank
|
May 16 2015, 05:31 PM
Post #5
|
- Posts:
- 639
- Group:
- Members
- Member
- #3,502
- Joined:
- July 11, 2011
|
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.
|
cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
|
| |
|
mmcc
|
May 18 2015, 02:00 AM
Post #6
|
- Posts:
- 3
- Group:
- Members
- Member
- #4,267
- Joined:
- May 12, 2015
|
- 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
|
|
|
| |
|
Karl-Uwe Frank
|
May 10 2016, 08:19 PM
Post #7
|
- Posts:
- 639
- Group:
- Members
- Member
- #3,502
- Joined:
- July 11, 2011
|
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
|
cHNiMUBACG0HAAAAAAAAAAAAAABIZVbDdKVM0w1kM9vxQHw+bkLxsY/Z0czY0uv8/Ks6WULxJVua zjvpoYvtEwDVhP7RGTCBVlzZ+VBWPHg5rqmKWvtzsuVmMSDxAIS6Db6YhtzT+RStzoG9ForBcG8k G97Q3Jml/aBun8Kyf+XOBHpl5gNW4YqhiM0=
|
| |
| 1 user reading this topic (1 Guest and 0 Anonymous)
|