Measuring Cryptographic Strength – Practical, Perfect & Ideal Secrecy

BRIEF HISTORY OF MODERN CRYPTOGRAPHY

The year is 1945, and Claude Shannon publishes a classified summary paper which is the foundation to modern cryptography – “A Mathematical Theory of Cryptography” (https://www.iacr.org/museum/shannon/shannon45.pdf).  Following declassification of the first paper, he expands on the previous paper and publishes a more comprehensive paper on Cryptography in 1949 – “Communication Theory of Secrecy Systems” (https://pages.cs.wisc.edu/~rist/642-spring-2014/shannon-secrecy.pdf).

In his papers, Shannon proposes 3 security standards based on the concept of equivocation – equivocation being the length of ciphertext required where a brute force key or message attack would result in a single viable message being produced:

• Perfect Secrecy – Claude Shannon defines Perfect Secrecy as a system where the key and the message are of equal length. In this context, an attacker performing a brute force attack would encounter all possible valid messages, including one correct message and numerous incorrect ones. The security of the system is provided by the incorrect messages, making it impossible for the attacker to determine the correct one without the key.
• Ideal Secrecy – Ideal Secrecy, on the other hand, involves repeating or extending the key when the message is longer than the key. Security can be maintained if the length of the ciphertext does not exceed a certain threshold. This threshold is determined by equivocation, which is the length of ciphertext required to ensure that brute force attacks produce multiple valid messages, thus maintaining security. Shannon’s concept of equivocation is crucial in this regard, as it guarantees that no single valid message can be conclusively determined from the ciphertext. With English, using a 256-bit key, (32 characters if using ASCII) any message longer than 37 characters is almost guaranteed to produce a successful decryption under brute force.
• Practical Secrecy – Where messages are longer than the key, necessitating a repetition of key, one may consider the amount of work required to brute force an encrypted message as adding a measure of difficulty. Note that such a system has no secrecy – since multiple valid messages are not guaranteed. Even then there is a caveat to be met – It must be proved that no fast solution exists.

With existing cryptographic primitives and techniques, there are some major challenges with Perfect Secrecy, Ideal Secrecy, and Practical Secrecy

• Perfect Secrecy – The One Time Pad that is an example of cryptographic primitive that provides Perfect Secrecy is almost impossible to implement in a digital context – we’ll explain why later in this blog.
• Ideal Secrecy – Requires an understanding of equivocation – so there are currently no practically viable solutions in the commercial security space.
• Practical Secrecy – The standard in use today where “difficult” mathematical problems are used to create ciphers – Shannon warned that it is not enough for such systems to be immune to all known attacks, they must be immune to all possible attacks. This requires a proof that a fast method of solving the maths problem is not possible.

Looking at our current state of cryptography (with 3 exceptions which we will soon cover):

• In over 70 years, in the commercial security space we have made zero progress in creating a secure practical encryption system.
• None of the security systems we use today are information theoretically secure. Thus, the need for the redefinition of security so that sub-standard systems can pretend to be secure – the so-called – “Notions of security” and “Complexity Theory”.

Whereas commercial cryptographic standards only consider Practical secrecy standards, the military require a higher cryptographic bar, with other differences detailed as follows:

• The military security definition includes Shannon’s definitions of security and consider any encryption to be secure provided equivocation never reaches zero.  Commercial security definitions are based on unsupported mathematical assumptions that problems are “hard” and use the workload characteristic to measure insecurity.
• The military have faster methods of attacking ALL security systems than is known to the commercial space (as expected). These solutions remain top-secret.
• Military risk management starts at the most undesirable risk conditions, and then looks for solutions with proof that risks have been mitigated. Commercial security risk management looks at the most favourable risk conditions and expects others to provide proof of a risk.

The main concern is that we are now entering an era where Quantum Computers and Artificial Intelligence are added to the attackers’ arsenal – this has already occurred in the military security domain. All current cryptographic solutions are at even greater risk. Worse still, some of the “hard” problems we use for security today can already be broken with classical computing solutions, with no need for quantum computers. We really must go back to the secrecy system drawing-board and reject these insecure “Notions of Security” and “Assumptions of Mathematical Complexity”.

Quantum Compute & AI Compute RESISTANT SECURITY SYSTEMS.

As mentioned previously, there are three security systems which are already Quantum Compute and Artificial Intelligence (QC/AI) Secure.

• The One Time Pad or OTP (in use for > 50 years)
• Quantum Key Distribution (EVOLVING field of Cryptography)
• Perpetual Equivocation (NEW field of Cryptography from Incrypteon)

We will cover these during the remainder of the blog, but before we do this, let’s define what we mean by Quantum Compute (QC) and AI Secure.

What is meant by QC and AI secure?

Any security system which satisfies Shannon’s Perfect Secrecy or Ideal Secrecy, must meet the security condition, that under a brute force key or message attack by an assailant with infinite time and computing resources (an assumption which flows from a QC/AI attack), on a ciphertext, more than 2 possible messages must result, of which one is the actual message that was sent. This is irrespective of any other condition – message length, key size, cryptographic operations etc.

A simple example – Take a pack of cards (52 cards), if the search condition is for Aces, then irrespective of the speed of computation or search, the search will result in 4 viable Aces – each of a different suite – each equally probable to be the actual Ace required. Such a system has a security index (the logarithm of the conditional entropy of Aces with respect to the pack) of 2 (4 = 22). With 2 packs, 8 results will occur, and the security index is therefore 3 (8 = 23). The security of a cryptosystem is calculated as the logarithm of the number of residual viable messages. Any system which can ensure that conditional entropy of key or message never attains zero under a brute force attack, is QC/AI secure. Note that 1 = 20, a single viable solution to the cryptogram – meaning it is solved.

With regards to assumptions – as the security system designer, you are not allowed ANY assumptions. The assailant is granted ALL assumptions, unless mathematically proven otherwise.

THE ONE TIME PAD.

With respect to our three candidates, the One Time Pad (OTP) – https://en.wikipedia.org/wiki/One-time_pad – and any other system is theoretically unbreakable if the following conditions are met:

• The key must have as much entropy as the information in the message – For simplicity we say the key must be as long as the message, but strictly speaking this is not correct.
• The key must be random – uniformly distributed and independent of the plaintext. Pseudo random number generators and so called “cryptographically secure” random number generators are NOT random.  ALL possible number sequences must be possible, all equally probable.
• The key must never be reused – in any format, in part or in whole, or a derived variation of the key.
• The key must be kept completely secret – during creation, exchange, use and destruction by all parties to the communication.

Practically, the above has been used in the military analogue world to send messages using codes written on flash paper. However, it is impossible to practically apply the OTP to a digital military context.

For practical considerations, the OTP has a number of challenges:

• The OTP Key Length Problem – For today’s digital communications, an almost infinite length of OTP random key is required. OTP key material supply must match OTP key need. In a military context, this requires the creation of Terabytes of OTP key stored on a digital device. It is not possible to secure such a device, and OTP keys run out pretty quickly.
• The OTP Key Generation Problem – Again, one cannot use pseudo-random number generators – these will only produce as many key sequences as the keys used to initialise the PRNG. At least one true source of entropy is required. Note that pseudo-random number generators are NOT cryptographically secure.
• The No Reuse Requirement – This includes ANY reuse of the key – as ephemeral, in whole or in part – in a derived manner. No exceptions. Ordinarily not a problem.
• The Secrecy Maintenance Problem – At least two copies of the OTP key are required. In practice, digital key storage devices are used. These are prone to theft, copying, destruction due to military explosions, and must be encrypted with another security system. This renders the OTP key only as secure as the encryption used to secure it. These keys must be physically distributed, and under practical application, require key storage devices to be inserted into computing systems, which are not secured with OTP keys. You can only secure an OTP key with another OTP key if you encrypt it. Also, any part of the OTP key that has already been used MUST be destroyed immediately. This makes for very impractical situations – secure parts of the key with different encryption keys? – decrypt the entire OTP key or section, edit and re-encrypt?
• The Passive Breach Problem – There is no method available to indicate that a breach has occurred. There is no breach auto-recovery mechanism. Also, it is prone to errors, and to enemy interference – where they create false messages to expedite OTP Key depletion, forcing reuse.

In short, OTP digital implementations have too many practical challenges in meeting the requirements for digital implementation. It’s very effective but limited.

QUANTUM KEY DISTRIBUTION.

Quantum Key Distribution (https://en.wikipedia.org/wiki/Quantum_key_distribution) entails the use of quantum computing hardware technologies to replicate the Perfect Secrecy characteristics of the One Time Pad.

In effect, it is an OTP hardware solution, entailing the following:

• Quantum Random Number Generators producing One Time Pads of unlimited length.
• OTPs are transmitted across fibre to sender and receiver nodes – Quantum principles allows for detection of evesdropping.
• Sender combines OTP with message to encrypt, receiver reverses ciphertext with his OTP key.

QKD’s approach to solving the OTP Implementation problems is as follows:

• The OTP Key Length Problem (Limited Solution) – Quantum-based hardware random number generators are used BUT – there are practical limits in terms of the rate of good entropy which can be produced – around 50 Mb/s, so there is a scalability problem. In addition, there are error conditions which limit the entropy production rate. Quantum RNGs can be combined with pseudo-random RNGs for speed.
• The OTP Key Generation Problem (Solved) – Again, quantum Random Number Generators produce good quality random numbers.
• The No Reuse Requirement (Solved) – OTP keys are sent continuously, and don’t need to be reused.

The Secrecy Problem (Unsolved) – This area remains problematic.

• OTP keys must be sent simultaneously to sender and receiver. This entails that receiver should securely store the OTP locally if he requires decryption at a later point in time. This requires a mechanism for securely storing an OTP locally. In addition, securing OTPs requires another OTP, otherwise the OTP is only as secure as the security used to protect it.
• The storage problem is compounded, in that stored OTPs must be destroyed immediately after use. Technically, in a digital environment, any OTP storage facility poses a security risk – It can be damaged, corrupted, stolen.
• In addition, the secrecy condition imposes limitations on implementation – can only send OTPs across a single fibre link, so limited to 50 KM range. In addition it cannot be used with wired links or fibre links with repeaters (susceptible to man-in-the-middle attacks at the repeaters)

The solution is limited to securing data in transit. For data at rest, there is the issue of having to store the OTP somewhere, with another OTP, which itself must be stored with another OTP. infinitely. So technically does not satisfy the OTP requirements for wired connections or securing data at rest. Remember that OTP MUST be secure against an assailant with unlimited resources and time.

PERPETUAL EQUIVOCATION

The Achaios Protocol from Incrypteon is a state-of-the-art next-Generation encryption system which has been patented – in that it combines a large number of new cryptographic concepts:

1. Information Theoretical Security using Entropy Addition – Archaios is mathematically secure against a quantum machine (or whatever comes after that) because of Perpetual Equivocation and Entropy  Augmentation. It is the only known encryption algorithm which can add entropy to the system at a faster rate than can be lost when a quantum machine performs a brute force attack of all possible keys). It was designed to beat a machine at its own game – check out our white papers for more information.
2. Multi-Dimensional Design – Archaios uses at least 3 input types during encryption. Messages M, keys K and an infinite length random string R. Every ciphertext is unique, even if using the same message M and keys K. Ciphertext cannot be replayed.
3. Security-In-Depth Design – Multiple OTP Encryption Zones – There are at least 2 encryption zones (Zone 2 is secured inside Zone 1). Basic OTP encryption operations on Multiple Messages and Random strings are performed separately in Zone 2, then Zone 2 outputs are shuffled and jointly OTP encrypted in Zone 1. Embedded OTP encryption guarantees that keys remain unknown, even if the message is known. The Security Zones design provides security in depth using a second information theoretic security layer (paranoid design – just in case- we assume the message has been compromised)
4. Random Mechanics – Kolmogorov Complexity – Kolmogorov complexity is added to the usually fixed and static (deterministic) mechanics of encryption by making operations dynamic and random (probabilistic). Each encryption operation on a message M, will have random lengths of M, random lengths of infinite random message R, and the order and type of encryption can be determined randomly.
5. Cryptographically secure random number OTP Key Generation with Entropy Recycling – We use at least 2 RNGs (random number generators) to create entropy for random strings and generate OTP keys. True random number generators can be added in a simple manner. OTP keys are never stored, but only generated at the specific time they are needed (ephemeral OTP)  – solves the OTP creation, storage and destruction problems. Since keys are not divulged, RNG entropy can be discarded and recycled – solves the entropy depletion problem.
6. Cryptanalysis Countermeasures – Cryptanalysis requires message ciphertext and keys to perform a brute-force key search. Since message ciphertext is mixed with random ciphertext and encrypted with an OTP, cryptographic resistance is provided in that the attacker must consider all possible message/random ciphertext values. The same applies to the OTP keys. Since the keys differ in length and quantity and are generated from an RNG state of random values, of unknown length, he must determine all possible key values. Once he has done that, he must construct all possible RNG state values. Cryptanalysis must solve a very difficult problem to perform a brute force attack. It MUST bridge the gap between all possible yet unknown plaintext/random messages with all possible yet unknown RNG states. That is at least 2 degrees of separation – most encryption algorithms have none. And he must solve the problem within this encryption step, as the RNG state is guaranteed to refresh itself in the next encryption
7. Artificial Intelligence – Archaios allows for the introduction of managed Artificial Intelligence agents, to perform specific security activities, thereby removing human intervention. This is currently in R&D.
8. Perfect Forward Secrecy in Operation – Not a new concept, but included nevertheless. After a message has been encrypted and sent, the state of the system can be saved for later
9. And there’s more – In OTP Zone 2, you can run any cryptographic construct on the message in an information theoretically secure context – authentication, repudiation, hashes, passwords, etc. You can create your own variants using any encryption algorithm – but beware of algorithms which can be run in hardware – they are insecure. There are techniques for randomising code pages, reducing the redundancy in messages (documents have so many zeros) thereby improving the Entropy Addition efficiency.