The best cryptographic protocol ever!

Cryptographic protocols are broken so often. Current crypto protocols use outdated algorithms. They’re usually incomplete, leaving multiple insecure choices to implementers. This post will solve all these problems once and for all. We will use modern crypto algorithms which are safe against powerful quantum computers. Furthermore, we will modify state-of-the-art algorithms to make them faster, safer and easier to use. We will specify practical deployment guidelines to mitigate all known practical attacks. Finally, our protocol is based on solid cryptographic foundations and are proven safe in the standard model, i.e., attacks are impossible.

To completely specify our protocol, we will describe key exchange, key server, digital signature, side-channel protection, record encryption, replay attack protection and compression algorithm.

Key exchanges

We recommend 2 safest algorithms

Matrix-based key exchange

Nowadays, it’s known that Diffie-Hellman (DH) key exchange is mathematically broken . To see how, let me describe the DH key exchange.

1. Alice → Bob: xG
2. Bob → Alice: yG
3. The shared secret is y(xG)= xyG= x(yG).

Advanced math tells us that there is a map from xG to x, so using the described map, knowing xG, yG helps finding the secret x, y and hence the shared secret xyG.

Therefore, we will use advanced lattice-based key exchange instead of DH. Don’t be afraid of the terminology lattice, they’re just matrices that you’ve learned in your undergrad course. Matrix-based key exchange is proven safe against quantum computers and hence it’s safe against classical computers. The drawback of matrix-based key exchange is it has noise. Noise is annoying, no one likes noise. We will modify state-of-the-art matrix-based key exchange to completely remove noise.

The protocol where A is a matrix.

1. Alice → Bob: Ax
2. Bob → Alice: yA

3. The shared key is (yA)x = yAx = y(Ax).

Our protocol is proven safe based on the below theorem.

• Quantum resistance matrix assumption (QRM): given matrix A and vector Ax, it’s impossible to compute x even with the help of quantum computers.
• Theorem: Our matrix-based key exchange is safe against eavesdropping adversaries if QRM is true.
• Proof: Only available in the extended version upon request.

Quantum key distribution (QKD)

QKD’s security doesn’t depend on the shaky ground of hard computational problems. Its security depends on quantum physics that no one understands, let alone breaks it. The core idea is that if the attacker (Eve) eavesdrops on the communication then both Alice and Bob can detect it based on the quantum measurement principle. Europe invested billions of dollars on QKD, so its security is guaranteed.

Digital signature

The drawback of the above key exchange protocols is that they’re unauthenticated. Therefore, we need a digital signature algorithm. Standard digital signatures such as ECDSA or Ed25519 are simple and not trendy, so we won’t use them.

We’ll combine 2 best digital signatures into 1 digital signature that is short, aggregable and safe against quantum computers. Our proof of security is based on the following generic theorem.

• Composition theorem: when we combine 2 safe protocols, the result is a safe protocol.

Quantum safe digital signature XMSS (eXtended Merkle Signature Scheme)

XMSS are standardized by both IETF and NIST, so its security is guaranteed. While XMSS is safe against quantum computers, it has a significant drawback. It’s stateful , i.e., it maintains state. No one likes states, so we will completely remove its state by keeping the secret key constant over time. This opens the door for distributed systems where sharing states is very difficult. By removing the state, we increase the speed by 128 times using 16 servers, each having 8 cores where parallelization is trivial.

BLS aggregate signatures

BLS signature is a pairing-based signature which uses the following beautiful property e(xP, yQ) = e(P, Q)^(xy). BLS aggregate signatures can combine millions of signatures into 1 short signature. Instead of keeping gigabytes of signatures, you can just store 1 single 48 byte aggregate signature. According to IRTF’s document, BLS signatures have no weaknesses. To add to the perfectness of BLS signatures, we will modify the pairing protocol to make it faster and constant-time. If we define e(P, Q) = 1 then e(P, Q)^(xy) = 1 for all x, y. Therefore, the pairing’s computation is super fast and constant-time.

Sign-sign algorithm

The sign-sign algorithm allows the combination of 2 signatures. It is simple yet elegant. To sign a message m, we first use XMSS to compute the signature y = XMSS(m). We then treat y as the input of BLS signature, i.e., we compute BLS(y). In summary, the signature is simply BLS(XMSS(m)). This algorithm is safe against quantum computers because XMSS is safe against quantum computers and it’s aggregable because BLS signatures are aggregable.

Transparent key server

Cryptographers often don’t discuss the important topic of key servers. We will avoid that mistake by specifying concrete key servers’ architecture. Google has a project called key transparency, but it’s not popular because it’s not transparent enough. We will define a fully transparent key management system. In fact, we will propose 2 key management systems.

RESTless key server

Our key server works all the time, it never stops and that’s why it’s called a restless server. It supports GET requests where everyone can retrieve the public keys and it supports POST requests where anyone can submit their public keys to the server. Therefore, this server is open, transparent and safe.

Blockchain-based key server

While the above RESTless server is awesome, it’s not safe against denial of service attack and censorship. We want a key server for everyone in the world, independent of geographic locations. Therefore, we propose using the block chain to store our public keys.

Furthermore, we think that a simple blockchain is not enough because the blockchain leaks the public keys. Therefore, we’ll deploy zero-knowledge proof to prove the existence of public keys without even revealing them.

Side-channel protection

Standard cryptographic protocols don’t deal with key leakage problems and hence cause countless vulnerabilities. We propose 2 main enhancements.

Using leakage-resilient cryptography

Leakage-resilient cryptography is safe against “smartass” attackers. “Smartass” attackers are attackers who compromise the victim’s system, and have the capability to read the whole secret key, but the attackers don’t care, the attackers only read half of the secret key and run away. Using novel leakage-resilient cryptographic protocols, we don’t have to worry about smartass attackers anymore.

Constant-time signature verification

One of the forgotten problems in cryptography is constant-time signature verification. Traditional cryptography only cares about constant-time signing which leads to vulnerabilities in verification. Using our novel constant time mapping above, we can achieve this goal easily.

Compress-encrypt-compress algorithm

Cryptographers often don’t specify compression which causes significant bandwidth loss. We propose enhanced compression by compressing both the data and the ciphertext, i.e., to encrypt plaintext m, we do the following: compress(encrypt(compress(m))). This saves bandwidth and is super safe.

Record encryption

To encrypt a message, we will break the message into small 16Kb packets and encrypt each packet independently. This packet level’s stateless encryption is an enhancement over slow and cumbersome stateful encryption.

Replay attack protection

To avoid replay attack, we use Galois Counter Mode (GCM) encryption where the counter starts at 0. Both sides will keep increasing the counter and hence if the attacker replays the old packet with the old counter, we can detect it. We understand the expensiveness of key exchange, so when we resume a lost connection, we reuse the shared key, but reset the counter to 0.

Random number generator

Random number generator is crucial to security and hence we propose 2 enhancements.

Optimized modulo operation

Typically, the OS only allows us to generate random bytes. However, in practice, we need to generate a number in a specific range (0, x). By using optimized modulo operation (%), we can generate a random number in a range really fast by randomizing 8k bits and then % x.

Rejection sampling algorithm

Not all numbers are the same. For instance, 0 and 1 are guessable. Therefore we have a ban list of bad numbers and if the random number generators accidentally generates them, we will reject them.

Patent issue

I filed patents to protect intellectual property of my best cryptographic protocol. You can enjoy it, but you can’t use it in production without my explicit permission.