Introducing PolyCrypt

Some time ago, a user named Steven uncovered a weakness in the FibonaRNG cipher, leading to this other post as a reply. At that time, I did not think that FibonaRNG needed to be strengthened, but recently I have realized that it would not be very difficult to remove that weakness. The result is PolyCrypt. The “Poly” bit comes from the fact that it can not only add security, but also remove it, making it a good platform to test classic human-computable ciphers.

The weakness that Steven found is basically this: every letter in a FibonaRNG keystream results from the sum or subtraction of two consecutive letters located earlier in the keystream, what is called a Lagged Fibonacci Generator (LFG). If an attacker can figure out where a keystream bigram is repeated, he/she/it can then figure out where keystream letters will be repeated, since they would derive from the same previous two letters. The keystream is sure to have many repeated characters, but knowing where they are is very bad because then the ciphertext letters at those locations would be encrypted by the same keystream letter, and any departure from statistical randomness of the plaintext would be reflected in those ciphertext letters, allowing statistical analysis.

It turns out that adding the plaintext serves to hide the keystream, so that it is very difficult to identify the location of repeated keystream letters if one only has the ciphertext, but let’s imagine for a moment that an attacker can do that. Repeated bigrams are not uncommon, appearing every 31 characters on the average because of the birthday paradox. So we can expect a keystream letter to be repeated within a relatively short distance not only because there are only so many different letters, but because a repeated bigram will cause a repeated letter some distance down the keystream (we don’t know which letter, though).

One way to prevent this, then, is to make keystream letters depend on three previous letters rather than two. A particular trigram is 24 times less likely to appear than a bigram because it has an extra letter, which leads to an average spacing between repeated trigrams, for a probability over 50% of finding a repeat, of 148 characters, according to this online calculator. This distance is comparable to the entire length of a message likely to be encrypted by hand, so the predictable keystream repeats won’t be enough to permit any statistical analysis. If we make keystream letters from the combination of of four previous letters, an attacker will need tetragrams to be repeated, but these are more than 600 characters apart on the average. Involving more keystream letters does not amount to a lot of extra work if done via “serpentine” operations on a Tabula Recta where the sender looks up the first letter on the top header, for instance, then goes down that column to find the second letter, then sidewise to the third, up or down to the fourth, and so on, finishing off by moving perpendicularly to the last motion to read the output letter on the right or bottom header. Each leg of the serpentine operation is equivalent to subtracting the previous result from the new letter reached.

So PolyCrypt has been designed to use a variable number of consecutive keystream letters to obtain a new keystream letter by following the operation described above on a Tabula Recta. Additionally, the headers can perform substitutions automatically. The header at top incorporates the substitution resulting from key 1; the header at left, the one resulting from key 2, and the headers at right at bottom, the substitution resulting from key 3. Thus, making the keystream involves key 1 at the start of every serpentine operation, and key 3 at the end (result is read at right or bottom). Combining the plaintext with the keystream involves keys 1 and 2. Key 1 is reused for the final combination because a plaintext substitution prior to combining the result with a keystream adds less security than a ciphertext substitution done after the combination, as this paper explains, so key 1 has a lesser impact on security.

The keystream seed should be random for best security, so key 4 is not the actual seed but a string used to mask the seed before it is sent along with the ciphertext. But the app allows users to use key 4 as the actual seed so classic ciphers can be emulated. This is done by unchecking the “Random seed” checkbox. Security should be very good simply from the keystream and substitutions, but PolyCrypt also incorporates a columnar transposition of the ciphertext, keyed by key 5, to emulate traditional ciphers that use transpositions. If users wish to perform an unkeyed transposition, they only need to write an integer number as key 5, indicating the row length of the transposition table. Leaving key 5 empty skips the transposition.

Finally, PolyCrypt performs two types of plaintext processing. One is the trick used in PassLok Human for preserving spaces and some punctuation: convert Q’s to K’s, then spaces to Q’s. The other is a “cut” at some random point in the plaintext, with the halves being recombined in the opposite order, with a marker (the word “polycrypt”) between them. The latter makes known plaintext attacks based on stereotyped content more difficult by starting the predictable plaintext at random locations.

PolyCrypt features a very large maximum key space, of size 26!^3 from the substitutions alone, to be multiplied by the (variable) sizes of seed and transposition. If we are using 10 characters for those, then the size of the key space is 26!^3 x 26^10 x 26^10 = 1.3E108, equivalent to 360 binary bits. This makes a brute force attack impossible with current technology. Attacks that work on computer ciphers, such as “meet in the middle“, do not work because PolyCrypt does not consist of many repetitions of a relatively simple calculation, as computer ciphers do, but of intrinsically complex calculations done only once. Known plaintext attacks cannot retrieve key material, such as keys 3 and 4, that are used exclusively for keystream generation.

Hopefully readers will tell me, in the Comments to this article, if they find any vulnerability. There’s also the GitHub page containing it along with my other human-computable ciphers in case they want to improve it directly. So let me finish the article by sharing some recipes to make PolyCrypt emulate traditional ciphers. In all examples, the plaintext will be the first sentence of Dickens’s “Oliver Twist” (gutenberg.org edition) without spaces, which reads:

Among other public buildings in a certain town, which for many reasons it will be prudent to refrain from mentioning, and to which I will assign no fictitious name, there is one anciently common to most towns, great or small: to wit, a workhouse.

Caesar cipher:

This cipher shifts letters by the same amount in the alphabet, equivalent to adding always the same letter as keystream, so use no keys except for single letter in key 4. No random seed. 1 letter involved in keystream. Without additional tricks, PolyCrypt performs a subtract operation, so to add letters instead as in the traditional Caesar cipher, use the negative alphabet “azyxwvutsrqponmlkjihgfedc” as key 1.

with shift = 13, which means key 4 = “N”. the resulting ciphertext is:

NZBAT BGURE CHOYV POHVY QVATF VANPR EGNVA GBJAJ UVPUS BEZNA LERNF BAFVG JVYYO RCEHQ RAGGB ERSEN VASEB ZZRAG VBAVA TNAQG BJUVP UVJVY YNFFV TAABS VPGVG VBHFA NZRGU RERVF BARNA PVRAG YLPBZ ZBAGB ZBFGG BJAFT ERNGB EFZNY YGBJV GNJBE XUBHF R

Vigenère (so-called) cipher:

Now the keystream consists of repetitions of the same password. No keys except for password consisting of several letter in key 4. No random seed. 1 letter involved in keystream. To do additions instead of subtractions, use negative alphabet “azyxwvutsrqponmlkjihgfedc” as key 1.

with key 4 = “KEY”. Result:

QIQXK MJDGB TSRHK MFSYH FSREI EPKGC HPCSR RESPG LGSDH YVKQJ ABIYI KPCMR MENVF CFNWN ILJPQ BIDHW KXJPE IOORR YKPSR EQJFD SUXEE RMUYH NKWQY CPXSD YYVSX GEQUX EKUPJ OVCYO QXIYD YKORR BUEYQ KEJVY QMIPV YALIC TOERE NUWEJ BPQGM RQSQB OFEQU O

Substitution:

This is what was used in Edgar Allan Poe’s “The Gold Bug” story. Use the substitution alphabet as key 1 (omit last character if using an entire alphabet), negative alphabet “azyxwvutsrqponmlkjihgfedc” as key 2, single “A” as key 4, 0 letters involved. No random seed.

with key 1 = “Gold Bug”, which leads to this substitution alphabet = “GOLDBUFZYXWVTSRQPNMKJIHECA”. Result:

ZSBRA BMWXO QFECV YEFVC DVRAN VRZYX OMZVR MBKRK WVYWG BOSZR IOXZN BRNVM KVCCE XQOFD XRMMB OXGOZ VRGOB SSXRM VBRVR AZRDM BKWVY WVKVC CZNNV ARRBG VYMVM VBFNR ZSXMW XOXVN BRXZR YVXRM CIYBS SBRMB SBNMM BKRNA OXZMB ONSZC CMBKV MZKBO TWBFN X

Transposition:

This can be combined with any other cipher, but here let’s use it just by itself. No keys except the transposition key as key 5. 0 letters involved in keystream making.

with key 5 = “transposition”. Resullt:

OCCIS RIIIF ECTEI PGONL RNWIU OOWLO EINMW TMTSI IYTMK BINRB FIINN EMSTS NBECO UNNWI TIOAT USWYL ETHGS NMNLU TLAOI NONLI RTSRO OITFS ERALT ENOOW MIAHA PANHO MNNRW HDIRT TMDAT ELTSR GURHN DFGIC HEMTA RNTAI OEOSO SCOAH ALNWE EROCN AAOGO E