BitFlip Collision Study
Manual Collision Test
Automatic Collision Test
The BitFlip cipher assumes an alphabet comprised of t letters, where each letter is represented by a secret key in the form of a random string of n even bits. To communicate a letter from the alphabet, the transmitter will randomly flip f bits. Nominally f= 0.5n (half the size of each letter key), and thereby generate the respective cipher-letter. The receiver will recognize the transmitted cipher-letter by it having exactly f bits flipped when compared to the key of that letter. And having no other letter which is exactly f bits apart from the communicated string. The transmitter, therefore, will have to check the randomly created (randomly flipped) cipher-letter against "collision" -- namely against the possibility that the cipher-letter will have f bits apart from the letter it is supposed to encrypt, and having f bits apart from one or more other letters. Because in that case the receiver will be confused as to which letter the transmitter wishes to communicate. Illustration a=100111 and b=111011 have 3 bits apart (bits 2,3,4 counting from the left).
This brings up the question of the chance for a randomly generated (randomly flipped) cipher-letter to be in "collision" with another letter (which is to be avoided). Because BitFlip is ultra fast, it is not a big issue, if the transmitter has to try 5, 10, even 20 times before it gets a collision-free cipher-letter. In fact theoretical considerations conclude that the more difficult it is to get a collision-free cipher-letter, the more secure the cipher. Therefore ultra secure transmissions may be using a ratio of 100:1 of collision v. no-collision, to generate more security. While nominally one would flip exactly half of the bits in the letter key, this value may be varied, in order to reduce the frequency of collisions, in certain applications. The setting where f=n/2 is highly recommended because it maximizes the entropy. This means it increases the chance for equivocation which will render BitFlip unbreakable in a mathematical sense. In applications where the number of flipped bits varies from half point, this variance should be kept at minimum, and its value should be part of the shared secret key. In some cases it might be of advantage to dynamically change the value of f. One important advantage of the BitFlip cipher is that it empowers the user to determine how much security to use, by simply adjusting the randomness setting on the cipher.
In this test kit, the value of f is uniform with respect to the alphabet, but various applications may select a different (secret) value of f, for every letter in the alphabet, further increasing the cryptanalytic burden.
The BitFlip cipher replaces algorithmic complexity with a stream of high-quality randomness. So the size of the cipher-stream that transmits the message is much larger than the stored message, as evident from the size of the letter keys (which is also the size of the cipher-letters).
This BitFlip cipher must insure high quality randomness for the letter keys, as well as high-quality randomness for the flipping selection. One way to check the quality of a randomness source is to compare its results with the mathematics.
The Operational Modules
This study kit is comprised of (i) manual collision test, and (2) automatic collision test. The randomness source in this study is the plain pseudo-random number generator built into PhP.
Manual Collision Test
In this module, the user enters the number of letters in the chosen alphabet (t), the number of bits in each letter-key (n), which letter (1...t) to encrypt, and the number of bits to flip (f). Once selected, the usr clicks on the "Encrypt!" button, and the results appear momentarily: the letter key of the selected letter shows (bit string), then the random flipping of f of its bits, (the cipher-letter), and below that a list of how many flipped bits are there between the chosen cipher-letter and each of the t letters of the chosen alphabet. The bottom line states: "Collision Detected" or "Collision Free". The user may click the "Encrypt!" button again and again, to her full delight, and get a feeling as to how often one achieves the desired "collision free" result.
The user then may change any parameters: the size of the alphabet, the size of the letter key, the choice of the letter to encrypt, and the number of bits to flip.
For information, for letter keys not longer than 100 bits, the selected letter keys are printed on the bottom of the page.
Every time the study is run, a new alphabet key is randomly generated.
Automatic Collision Test
In this module the user also selects the size of the alphabet (t), the even number of bits in each letter key (n), the number of bits to flip, and the number of flipping rounds to run on this test. Once selected, the user clicks "Encrypt!" and the results show momentarily: First the mathematical chance for no collision, as calculated from the following formula:
Pno-collision = (1-x)t-1
Where:
x = n! / (f! *(n-f)! * 2 n)
This mathematical result is compared with the results of the rounds of randomly selecting alphabet with number of letters (t), and bit-size of each key-letter (n), and the number of bits to flip (f), as indicated. The letter to be encrypted (1...t) is randomly selected each round, and the statistics of how many cases of collisions and how many cases of no-collisions is reported below. The % difference between the theoretical result and the test results is also reported. This difference is because (i) the number of rounds is too small, and (ii) because the source of randomness is deficient.
You can vary the input parameters and check a variety of combinations to help you design the desired values for the BitFlip cipher you intend to use.
Collision rate may be well managed through setting the values of the three parameters that determine it: (i) the number of letters in the alphabet (t) -- the fewer letters, the fewer collisions, (ii) the size of the letter key (n) -- the more bits in the key, the fewer collisions, and (iii) adjusting the flip ratio (f) away from the 50% mark -- the further from 50%, the fewer collisions. The optimal setting depends on the application.
The important advantage of the BitFlip cipher is that in every possible setting the risk is accurately and credibly calculable by the user -- no risk associated with mathematical superiority of the adversary.