Infamous Crypto: Scratching the surface - Kleptography
How long do you want these messages to remain secret? I want them to remain secret for as long as men are capable of evil. – Neal Stephenson, Cryptonomicon
Introduction
This is the first attempt to bring a topic of personal study to an outside audience.
Attempt obviously limited in means and resources, but the goal is not to capture the reader as much as to construct a narrative of something I am personally experimenting with.
In the reading you will therefore go straight to the point without too many jumps and also some examples of original code (written by me) or referring to outside sources (always cited) to familiarize yourself with the topic.
There is no periodicity in the publication based on personal time and desire, but there is interest in writing some different topics.
This is cryptography
* Why do we talk about cryptography? And why is it not fully explained?
It is easy for me to answer these questions by making a simple quote, "Standing on the shoulders of giants."
More in detail I personally believe that cryptography, the real bare bones kind, is contemplating a
smidgen of the perfection of mathematics that has been "dirtied" in computer implementation and digging into the roots of good and evil.
Moreover, I do not pretend to explain to anyone topics as complex as they are precise, indeed it is likely that I may however careful commit some inaccuracies. Sorry.
* And why little math then?
Some parts will be reported for greater understanding, but not formally and completely, and I know what that means.
Fortunately, giants came before us who worked to prove, prove and disprove as much as possible allowing us to discuss complicated topics in a simple way.
* Why is it different from other blog posts?
Because it tries to combine brevity, concreteness with uncommon or unfamiliar topics.
Kleptograhy starting point
The topic we start with in '#1' talks about Kleptography:
"Kleptography is the study of stealing information securely (exclusively) and subliminally (unnoticeably)"
The first work about this topic was made by Adam Young, Moti Yun between '90 and '00. In the following years they dug deeper in this field.
Their first work related to this was:
- "Cryptovirology: Extortion-Based Security Threats and Countermeasures." in 1996
They have dozens of pubblications about that and cryptovirology, some examples (randomly selected, order by date) are:
- "Kleptography: Using Cryptography Against Cryptography." in 1997
- "Bandwidth-Optimal Kleptographic Attacks." in 2001
- "Kleptography from Standard Assumptions and Applications." in 2010
In particular Kleptography is a subfield of cryptovirology and is a natural extension of the theory of subliminal channels that was pioneered by Gus Simmons while at Sandia National Laboratory.
Note: In this article we won't talk about subliminal channels, but for the sake of reading they can considered as
covert channels that can be used to communicate secret information using unsuspicious communication over an insecure channel.
They were discovered by Gus Simmons in 1984 in Signature schemes.
Getting more into the specifics when a backdoor is inserted into an asymmetric encryption protocol in order to undermine one or more of its cryptographic security properties we talk about Kleptography.
If you think that such a trick is impossible take a look at 'Dual_EC_DRBG PRNG (NIST SP 800-90A)'
The majestic Diffie-Hellman Key Exchange
The Diffie–Hellman key exchange algorithm solves the following dilemma.
Alice and Bob want to share a secret key for use in a symmetric cipher, but their only means of communication is insecure.
Every piece of information that they exchange is observed by their adversary Eve.
How is it possible for Alice and Bob to share a key without making it available to Eve?
In matemathical language they have to choose:
A trusted party choose a strong prime (p) having a large prime order:
$$ p \in F(p) $$
A generator (g) of a finite cyclic group (G) that will be used modulo p, usually multiplicative.
Alice chooses randomly a private key (a) such that $$ a \in ( 1 \leq a \leq p-1 ) \land a \in N $$
BoB doest almost the same thing.
He chooses randomly a private key (b) such that $$ b \in ( 1 \leq b \leq p-1 ) \land a \in N $$
What does it means.
There a strong prime (p) that under a specific group operation is able to generate a large number of objects (order) of the Group.
The the group is finite so the number of integers is not infinite and is cyclic so after X operation they will repeat themselves.
Formally the order of an element of a group g (generator) in G (group) is how many times you have to repeat the group operation of g to get to the identity.
When the parameters are defined Alice and Bob calculate:
$$ A = g^a, B = g^b $$
both of the modulo p. This means that the protocol is introducing the Dischrete Logarithm Problem (DLP) problem making it virtually impossible for the attacker to recover the secrets: a,b.
After that they can send the following triplet (g,p,A) and (g,p,B) over the public channel and Eve will read them. However Bob and Alice are able to compute the secret, the shared secret modulo p.
$$ secret = B^a \equiv (g^b)^a \equiv A^b \equiv (g^a)^b$$
If everything is done correctly Eve is not able to solve Discrete Logarithm for A and B and retrieve b or a. The key is correctly exchanged.
For short reference: https://www.math.brown.edu/johsilve/MathCrypto/SampleSections.pdf
A not so fake scenario
The scenario is a fake company H3ck1v4t10N that write and sell a new super-secure tool called "closedssl", a faster openssl implementation and some customer buy it to implement in his protocols.
Because the binary is closed source and highly priced and its about cryptography not many research are interested to reverse and analyze it the process of the backdoor goes smooth.
What happened here?
H3ck1v4t10N company re-wrote Diffie-Hellman (DH), that is the base for secure channel creation on asymettric encryption, introducing its backdoor.
Their implementation make the standard protocol works but the subtle change can lead to breaking secure channel creation.
More specifically In cryptography, there are two ways to create a secure channel between two parties:
- The first one is to rely on a trusted third party.
- The second one is to rely on the trust the two parties have in each other.
Channels but it's not a TV
There are 3 main channel based on the property that they can prove:
In cryptography:
- a secure channel is a means of data transmission that is resistant to overhearing and tampering.
- a confidential channel is a means of data transmission that is resistant to eavesdropping
- an authentic channel is a means of data transmission that is resistant to tampering
As you can see a secure channel is based open the following two.
Diffie-Hellman key exchange builts secure channel. You can imagine that because if Alice receive another (g,p,B) from Eve, Bob can prove that the B was counterfeit (the algorithm fail) because the module congruences will fall.
In addition if data are encrypted using the shared secret Eve cannot modify them without losing the real information because she cannot solve the DLP thus decrypting and re-encrypting them.
We made a basic, and old, example using Naive DH Key Exchange. In modern days a lot of changes, improvements and tweaks were made, for example for Public Key Infrastructures (PKI).
However the concept still stands and the fundations still are built on top of that.
Let's see an example taken from: https://docs.oracle.com/javase/8/docs/technotes/guides/security/jsse/tls.html
Design our fictional Backdoor
There are two main path at this point to introduce a backdoor. The goal is to undermine the security of the exchange, in this example retrieve the key to decrypt the channel.
- 1) Target Random Number generation. If the randomness is not real and can be predicted the secret a or b can maybe be recovered and with (g,p) calculate A or B.
- 2) Target the Group G. If some properties are broken the DLP problem will becaome an 'easier' problem to solve and recover the parameters.
In the next phase the second option was pursued.
A couple of words about DLP problem, that makes everything secure.
In mathematics, for given real numbers (a b,) the logarithm log with base b for a is a number such that:
$$ log_b(a) = x | bx = a $$
Analogously, in group G, powers bk can be defined for all integers k, and the discrete logarithm such that:
$$ log_b(a) = k | bk = a \land k \in N$$
DH is considered secure because there ZERO algorithms to calculate easily the logarithm besides specific corner case. For this reason large numbers, modulo operations and some techniques are applied to select parameters - thanks Number Theory theorems <3
By targetting Groups we are weaking DLP resistance.
But you have to remember that (g,p,A or B) is public so the malicious company H3ck1v4t10N has to create a suite that seems real and legitimate - Kleptography definitions - but is vulnerable.
There several attacks and algorithms for DH and DLP, remember that. However keep in mind this is just an example.
One of the prerequisited about G is to choose a large Group. If we are able to create a sort of small group because of the cycling property it will be easier to break it.
We can fix a specific weak Groups (they exists) or create dynamically another kind of weakness, a Group that has small sub-groups. If this happens the DLP will fall.
One can imagine a safely chosen cyclic group as an entire planet without boundaries. In contrast, a cyclic group according to the properties of groups (which we recall constructed according to the same operation, ie multiplicative) in turn subgroups are constructed by the same operation and are cyclic. In this case it would be like putting in the planet a variable number of fences, until the whole land is divided.
The calculations made within the latter then obligatorily fall within one of the enclosures, and the cycle will form in an enclosure (subgroup) that is certainly smaller than the G-group.
Simply put, it is sufficient to introduce a smaller prime factor into the creation of the group, which in the metaphor personifies the fence.
It should be emphasized that this will not derive a or b, but a 'shadow' value that satisfies the logarithm according to the base.
Note:We won't delve in more details about how algorithms are being created to simplify and attack DLP.
Create a sneak new parameter q small random prime :
$$ q \in N \land isPrime(q) = 1$$
After that create (p) based on q and another strong prime (r). The result must be odd, thus +1:
$$ p = 2qr + 1 $$
At this point we are already weaking the protocol, but it can spotted because the generated number are short - in fact g is shorter than usual (bit length).
With our malicious parameter it is possible to evade this 'detection' by composing the generator using a short base but a large exponent.
$$ g = q^r $$
and to insert this generator in the protocol and observe used property calulate it mod p, g = q^r mod p.
Write you own backdoor in DH Key Exchange
This is my example for DH Kleptography implementation and i won't public the code to show how to break it.
If you think that is plagiarism about a public challenge in one of the main CTF platform it can be mine. There is a slightly modified version published.
#!/usr/bin/env python3
from Crypto.Util.number import isPrime, long_to_bytes, bytes_to_long
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from sage.all import *
from hashlib import sha256
from random import randint
'''
# Not perfect code, just a POC to try SAGE instead of python3
reference SAGEMATH: https://www.sagemath.org/
'''
class K:
def __init__(self):
self.gen_params()
def gen(self):
N = 2**21
'''
Trying to show step-by-step, can be collapsed in less operation and vars
'''
self.r = random_prime(2**1024)
self.q = random_prime(N)
self.p = (2*self.q*self.r)+1
while not isPrime(int(self.p)):
self.q = random_prime(N)
self.p = (2*self.q*self.r)+1
ZZn = IntegerModRing(self.q)
self.h = random_prime(N) # just to show every step
self.g = pow(self.h,2*self.r,self.p)
# can iterate for a little bit, you can create a faster example with shorter keys
while self.g == 1:
self.g = pow(self.h, 2*self.r, self.p)
ZZn = IntegerModRing(self.p)
self.a, self.b = ZZn.random_element(), ZZn.random_element()
self.ga, self.gb = pow(self.g,self.a,self.p), pow(self.g,self.b,self.p)
self.k = int(pow(self.ga,self.b))
def enc(self, shared_secret, input):
'''
This is an example to focus about the shared secret
so it is used its sha256 to encrypt something with AES ECB
'''
key = sha256(long_to_bytes(shared_secret)).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
ct = cipher.encrypt(pad(input, 16)).hex()
return ct
def get_gs(self):
return self.p, self.g, self.ga, self.gb
Ending
As you may have noticed some things are taken for granted or it is not necessary to know them fully to understand the meaning of what has been written.
The purpose of this conseapevol choice is to keep the length of the writing short and to allow for different keys to reading and insights.
If my intent is successful in fact, it will be possible to understand and follow by skipping some sections, perhaps for some people barring without losing the overall sense.
About the other option, the first one, i'll attach a reference from:
