SHADO Encryption Protocol


The SHADO encryption protocol has been developed by Keganzo in order to have a simple, fast and secure protocol to protect communications over an insecure channel, i.e. internet.

The SHADO encryption procotol is a brand-spanking new strong synchronous stream cipher1.

A stream cipher can be used to generate serially many keystreams2 from the same random initialization vector (IV)3.

Each keystream can be used to encrypt a message by XOR-ing4 it with the plaintext digits to form the ciphertext.

The stream cipher can be viewed as approximating a theoretically unbreakable cipher, the One-Time Pad encryption system5, proved to be secure by Shannon in 1949 but very cumbersome to implement in practice.

The main difference with stream ciphers is that one-time pads keystreams are generated completely at random with at least the same length as the plaintext and they aren't used more than once.

For a stream cipher to be secure, its pseudo-random numbers generator (PRNG) must have both a large period and at least a 256-bit length IV to make impossible to recover the cipher’s internal state from the keystreams. Moreover, keystreams must be free of even subtle biases that would let attackers distinguish a stream from random noise.

An outstanding feature of a synchronous stream cipher is that the sender and receiver must be exactly in step for decryption to be successful. If message digits are added, changed or removed during transmission, synchronisation is lost and tampering is detected.

The Mersenne-Twister (MT) PRNG is a good candidate to be the core of a stream cipher since it provides fast generation of high-quality pseudo-random integers, it has a vastly longer period (219937 - 1) and its IV can be up to 2048 bits long. Moreover, it passes numerous tests for statistical randomness as the Diehard tests6,7.

However, since MT is based on a linear recursion and the whole, huge sequence can be predicted with only a small sub-sequence of 624 numbers8, a secure hashing of the output must be achieved to make MT cryptographically secure9,10.

How the Encryption Works


Unique Session Keys Exchange by Diffie-Hellman + ElGamal

At the beginning of a communication session the two interacting parts generate unique cryptographically secure random 1600-bit length IVs on-the-fly (achieving perfect forward secrecy11). They negotiate those IVs by means of the Diffie-Hellman (DH)12 with ElGamal Authentication (EA)13 protocol, whose parameters are choosen accordingly to scientific literature (e.g. 10100-order random prime numbers). The ElGamal component ensures that the two parts authenticate and trust each other against tampering and a possible Man-in-the-Middle (MitM) attack, which would be the only vulnerability of a DH protocol.


The SHADO Stream Cipher

Each interacting part is provided with a stream cipher as the one outlined below. It is made of two Mersenne-Twister PRNGs whose interaction gives rise to a ciphertext encrypted with cryptographically secure pseudo-random keystreams.


The Keystream Mersenne-Twister PRNG

The first half of the exchanged IV is used to seed with an 800-bit length key a Mersenne-Twister PRNG (we called Keystream MT or KMT). The task of the KMT is to generate one-time keystreams for encrypting each message exchanged between the two parts at runtime (e.g., symmetric key cryptography), then reproducing the one-time pad behaviour. The KMT output is input in a multiplier, whose task is to compress information about the MT sequence iteratively and make it criptographically secure.


The Poisoning Mersenne-Twister PRNG

For the purpose of making the KMT cryptographically secure, one more MT (we called Poisoning MT or PMT) is seeded at the beginning of the session with the second half of the exchanged IV. The PMT determines the amounts of the KMT extractions to multiply iteratively. Only the most significative 8 bits of the resulting number are taken at each iteration. However, our PMT multiplies a random amount (in the range 8-32) of KMTs extractions, in place of taking a fixed sequence of 8 extractions, as done by Matsumoto et al.14. This way, the compressed sub-sequence which gives rise to the final PRNG output number is unpredictable enough against the 624-sequence exploit. Even more: if the pseudo-random sequence generated by the KMT should run out of steam, next cycle would generate different poisoned numbers, that is, a completely new pseudo-random sequence, and so on for any further cycle with period (219937 - 1).

Protection Against Known Attacks


To decrypt a SHADO message or file you need to know either the KMTs and PMTs IVs and the exact one-time keystreams extracted by the KMTs poisoned by the PTMs. Any deviation from the right MT pseudo-random sequences would determine a decryption error which can be detected by the two parts as an attempt to hack the communication. Moreover, because of the perfect forward secrecy, guessing the right sequence of a session doesn’t enable you to decrypt past or future communications.


Brute-Force15

Because of the mathematical properties of one-time keystreams cryptography SHADO cannot be defeated by a brute-force attack.


Collision16 and other Cryptanalysis17

For the attack to be successful, the attacker must be in control of the input to the hashing function. This can’t be achieved in SHADO because the hashing function is seeded randomly with the secure Diffie-Hellman key exchange. Moreover, SHADO is secure against cryptanalysis attacks (known plaintext, chosen plaintext, chosen ciphertext) because of both the vastly longer period of the KMTs and the random poisoning performed by PMTs on the one-time keystream extractions.


Replay18

SHADO is immune to a replay attack since any deviation from the synchronised KMTs sequences poisoned by the PMTs would determine a decryption error. Playbacking an encrypted message would only bring to detect the hack.


Man-in-the-Middle19

SHADO is immune to a man-in-the-middle attack because it uses an ElGamal asymmetric key encryption algorithm18 for mutual authentication and detection of genuine vs. rogue interacting parts.

References