Lecture
Honey encryption — a type of symmetric encryption in which the ciphertext decrypts, under any admissible key, into a plausible plaintext .
In 1999, Douglas Hoover and Nat Kausik considered the problem of protecting a private key in public-key cryptosystems, specifically the secret exponent in RSA and the private key in DSA, and proposed an algorithm for masking this secret component with a password (a six-to-eight-bit string). In their work they argued that for such passwords, a dictionary search would yield a result of the same structure as the protected private key, and an attacker would not be able to distinguish correctly decrypted data from many other plausible but false decryptions until they tried to use the obtained keys to access the targeted resource through an authentication server. The server would detect several authentication failures and suspend access. Such an approach provides an additional security measure, which makes it possible, for example, to reduce the dimensionality of the key space .
Subsequently, systems for storing passwords were proposed that use a similar method of masking stored authentication data among a list of clearly fake entries, to prevent disclosure of the database if, for example, a password hash file were leaked.
Building on such masking systems, Ari Juels of Cornell University and Thomas Ristenpart of the University of Wisconsin presented a paper on honey encryption at the Eurocrypt[en] 2014 conference.
In early 2014, American researchers Ari Juels and Thomas Ristenpart put forward a new idea in cryptography that could potentially have significant practical applications. This idea is called “honey encryption” (“honey encryption”) and consists of encryption that, when the wrong key is entered, produces false but plausible-looking data. In their paper they present lemmas and theorems proving that their proposed idea is mathematically viable.
Honey encryption is designed to protect against attacks that use exhaustive key search. Such attacks amount to breaking the cipher by trying every possible key, which is equivalent to choosing random plaintexts from the space of all possible plaintexts under a discrete uniform distribution. This can be effective: although the attacker obtains any given plaintext with equal probability, most of them are extremely implausible, in other words the distribution of reasonable plaintexts is non-uniform. The protection mechanism of the honey method is based on transforming the plaintext space into a space in which the distribution of plausible plaintexts is uniform. Thus, an attacker guessing keys will often obtain reasonable-looking texts, and random-looking texts only rarely. This makes it difficult to tell whether the correct key has been guessed. In essence, honey encryption produces false data in response to every incorrect guess of the password or encryption key .
The security of honey encryption relies on the fact that the probability that an attacker will judge a plaintext to be correct can be calculated (by the encrypting party) at encryption time. This makes honey encryption difficult to apply in certain applications where the plaintext space is very large or its distribution is unknown. It also means that honey encryption can be vulnerable to “brute-force” attacks if this probability is calculated incorrectly. For example, it is vulnerable to known-plaintext attacks if the attacker has a “cheat sheet”, meaning that they possess a certain number of plaintexts and their corresponding ciphertexts; this makes exhaustive search possible even for data encrypted with the honey method, if this possibility was not accounted for during encryption .
One drawback of the algorithm is the problem of typos: if a legitimate user makes a mistake while typing the key, they will get a fake plaintext that nevertheless looks plausible, and they will have no way of realizing this. Also relevant is the question of generating a semantically and contextually correct false message that is convincing enough to fool an attacker. Generated messages must be hard to distinguish from real messages, while also following the rules and norms of the language, and at the same time concealing meaningful information from the original text .
Under today's common approach, an exhaustive search of all encryption keys is guaranteed to produce a result. Even if no MACs, digital signatures, or padding indicating whether decryption succeeded or failed are used during encryption, using an incorrect key causes meaningful data to be decrypted into a sequence of pseudorandom numbers that are often easily distinguished from real data by a computer or a human. The key length of many algorithms is such that an exhaustive search is simply infeasible; however, flaws in the cryptographic algorithm or its implementation often make it possible to replace an exhaustive search with a reduced one, greatly speeding up the process . A reduced dictionary search is shown in Fig. 1.
Fig. 1. The process of cracking a password by dictionary search (based on )
In their paper, the researchers propose an approach in which not only a partial but even a full search of all possible keys can turn out to be useless, thanks to a clever trick: using any key (correct or incorrect) to decrypt the data always produces a plausible result, which makes it extremely difficult to distinguish correctly decrypted data from forged data (Fig. 2). This can be very useful in systems where it is difficult to guarantee strong encryption, for example when deriving an encryption key from a password, as well as in many other applications.
Fig. 2. Diagram of honey encryption (based on )
Like any other concept, honey encryption relies on certain assumptions. In this case, an important assumption is that decrypting a ciphertext with the wrong key yields pseudorandom data, and it is precisely because of this that we can discard many decryption results as implausible. In Section 2 of this paper, this assumption will be put to the test using the RSA encryption algorithm . In addition, Section 1 will examine the joint use of honey encryption and the RSA algorithm in general, without tying it to specific data types.
Honey encryption involves three sets: the set of all messages 
(the message space), the set of all keys 
(the key space), and the set of so-called intermediate values 
(from the English Seed). Another important part of honey encryption is the distribution-transforming encoder, or DTE (from the English Distribution Transforming Encoder), which consists of two algorithms, encoding and decoding, that establish a correspondence between the spaces and . During encoding, the plaintext is mapped to an intermediate value using the DTE, and is then converted into ciphertext using some symmetric encryption method with the chosen key. The decoding procedure with the key returns the intermediate value, which the DTE then translates back into the correct message .
A message can be mapped to several intermediate values, but each value — to only one message. If several values are possible for a message, the encoding algorithm randomly selects exactly one of them. Thus, this encoding algorithm is randomized, while the decoding algorithm is deterministic. The number of values mapped to a message must be proportional to its probability. Thus, constructing a DTE requires knowing the discrete probability distribution of message occurrence[10].
When the wrong key is used, the ciphertext maps to a different value and, thus, decrypts into a false message .
A specific practical implementation of the honey encryption scheme could be organized, for example, as follows. All the messages in are sorted in some order, after which the probability 
and the distribution function 
of each message are computed. The DTE then maps the plaintext message to a range of values from , where the start of the range is determined by the distribution function and the end — by the probability of the given message. The DTE then randomly selects an element from this range, which is then encrypted using a suitable symmetric encryption scheme with the key 
to obtain the ciphertext. The decryption procedure is carried out, correspondingly, according to the same scheme and with the same 
. The DTE then determines the location of the resulting value , which corresponds to the probability value lying between the distribution function of the sought message and the one following it in the space . By looking up the correspondence table between the message and its , the DTE recovers the original text message[11].
11 — this is the ciphertext. During decryption, the ciphertext is again added modulo 2 with the key:
This is again the intermediate value, which is then mapped by the DTE to the original message. The message is decrypted again.
If an attacker tries a key, for example, 00, they add it to the ciphertext and get {\displaystyle 11\oplus 00=11}
, which decodes to blue. The attacker cannot determine whether this message is correct or incorrect[13].
Various adaptations of the honey encryption algorithm find application in protecting data stored in cloud storage; one example is an implementation[14] that provides additional protection for encrypted files beyond the user's password. If an attacker tries to gain access to encrypted data by trying password variants using the “brute force” method, instead of denying access, the algorithm generates an indistinguishable fake file linked to the original file. A similar system has been proposed for protecting applications used in internet banking[15].
At the ICASSP[en] 2016 conference, a concept was presented for an eavesdropping-resistant messenger that generates plausible messages when an attempt is made to attack the encrypted messages[16].
1. On the joint use of honey encryption and RSA encryption
The original paper on honey encryption states that not all cryptographic primitives can be used together with honey encryption. First, we obviously must not use MACs, digital signatures, or padding during encryption that indicate whether decryption succeeded or failed; and second, the encryption algorithm used must satisfy the property that “encrypting uniformly distributed plaintexts produces uniformly distributed ciphertexts”. A group of students from the Massachusetts Institute of Technology argue in their paper that this condition holds for the asymmetric RSA encryption algorithm. This is a well-known, thoroughly studied and standardized asymmetric algorithm that has been widely used for several decades.
To work with this algorithm, it makes the most sense to use the most popular product in its field – the powerful free library OpenSSL . When using this library, we are faced with the question of choosing a key length. A key length of 2048 bits is considered relatively secure today and is actively used for encryption in the TLS protocol, which protects most encrypted connections on the Internet.
The RSA algorithm is not usually used to encrypt large data packets – a hybrid cryptosystem is far more efficient in every respect (speed, ciphertext length, security), in which an asymmetric algorithm (for example, RSA) is used to encrypt the key of a symmetric algorithm (for example, AES), which is then actually used to encrypt the data. The RSA encryption algorithm imposes strict constraints on the size of the plaintext, which must equal the key size, that is, in the case of a 2048-bit key the plaintext must also be 2048 bits (256 bytes). In addition, the plaintext, represented as a number, must be smaller than the modulus n = p*q, whose bit length equals the key length, which narrows the plaintext space even further [10]. For example, a plaintext consisting of 2048 one-bits cannot be encrypted without additional tricks when using a 2048-bit key. We will have to take all of this into account.
The OpenSSL library provides the ability to use cryptographic padding during encryption, which makes it possible to strengthen the algorithm's security, as well as to encrypt data shorter than the key size [11]. More specifically, OpenSSL allows the use of padding according to the PKCS #1 v2.0 standard (the EME-OAEP algorithm), according to the PKCS #1 v1.5 standard, a modification of the latter for versions 2 and 3 of the SSL protocol, as well as using no padding at all [12]. Using padding here is not merely a matter of good practice but an urgent necessity. The three types of padding listed above have a rigid structure that would break the “honey” property of the encryption — if the padding bytes strictly specified by the standard turn out to be wrong, the attacker will realize that the current decryption result is invalid. A good solution would be to introduce a custom padding scheme best suited to the task of honey encryption.
What would a good padding scheme look like in this case? First, we would like to avoid the situation where the number obtained from the plaintext turns out to be larger than the modulus n. Since the modulus n most likely has its high-order bits set to one, and these bits are stored in the first byte, the plaintext must be padded on the left with zero bits to guarantee that it is smaller than the modulus. In OAEP, for example, the first padding byte is 0 (0x00), and we will do the same. For us, introducing such a byte is a forced necessity, since on average only one out of 2^8 = 256 decryption attempts will give a plausible result, but it is still worth doing.
Second, using RSA without padding is not secure, in particular because of a possible adaptive chosen-ciphertext attack [13]. After zeroing the first byte, we could pad with pseudorandom bytes starting from the second byte, and to resist a birthday attack the number of such bytes must be at least 32 (giving us 256 pseudorandom bits). The length of the actual data will have to be stored, in plaintext or encrypted form, somewhere else, since storing it directly in the padding would help an attacker separate correct decryption attempts from incorrect ones. So, at minimum 33 of the 256 bytes will have to be set aside for padding, leaving no more than 223 for meaningful data. If we need to encrypt fewer bytes, say 200, then we would use 32 + 23 = 55 pseudorandom bytes instead of 32.
Perhaps the assumptions made above, that we need to zero out at least the first 8 bits of the plaintext and then fill at least 32 bytes with pseudorandom data, were too paranoid. In that case we can improve the efficiency of our padding — making the attacker's task of separating real data from spurious data harder and/or encrypting more useful data in a single ciphertext.
So, the RSA algorithm does allow honey encryption to be used together with it, but doing so is heavily complicated and limited, which makes a hybrid cryptosystem a much better solution. By applying honey encryption before encrypting the data with a symmetric algorithm, and after decrypting the data with that same algorithm, we gain improved usability, stronger security and higher speed, while the symmetric algorithm's key itself can be encrypted with that same RSA without much trouble.
2. Verifying the claim about decryption results
So, let us show computationally that when a ciphertext is decrypted with the wrong key in the RSA algorithm we obtain pseudorandom data, and it is precisely because of this that we can discard many decryption results as implausible. A program [18] was written to solve this problem.
First, this program assembles the plaintext to be encrypted. It consists of padding (a zeroed first byte, followed by 32 pseudorandom bytes) and the actual data (the remaining 223 bytes), so its total length comes to 256 bytes. For the purity of the experiment, the data bytes will each time be just a single repeated one-byte value, using the extreme and middle values from the possible range (0, 1, 50, 100, 150, 200, 255). It is precisely when encrypting these strongly non-uniform plaintexts that a non-uniform distribution of the decryption results, if one truly exists, is most likely to show up. So, the resulting message is encrypted with a freshly generated public key, and then decrypted with the corresponding private key to confirm that the decryption is correct.
After this we mount an attack on the encrypted algorithm, attempting to decrypt the ciphertext with freshly generated secret keys. The RSA algorithm's software implementation is quite slow, since RSA – is an asymmetric algorithm, so when modelling the attack we will have to limit ourselves to 256 key-guessing attempts (attack complexity – 2^8), and also disregard the value of the first byte (as already mentioned, if its value is non-zero the decryption result is already implausible, but we ignore this). If the resulting decrypted text turns out to be larger than the modulus (which is impossible with correct decryption), we pick a new key for that iteration. After each decryption, except for the case “decrypted text larger than the modulus“, we will collect statistics on the frequency of occurrence of various bytes in the decrypted data, that is, in the last 223 bytes (the padding is of no interest to us). To check how well the resulting distribution matches a uniform one (which is exactly what ideal random data would produce), we will use the CHITEST function of the Microsoft Excel / OpenOffice Calc / LibreOffice Calc spreadsheet editors, which performs a statistical test of the hypothesis using the chi-squared criterion [14, 15].
The results vary somewhat from run to run due to the randomness of generating the 32 padding bytes, the encryption key, and the decryption keys, but qualitatively, in essence, they stay the same when the experiments are repeated. The degree of similarity between the decrypted and pseudorandom data: for the numbers 0 – 0.24 (in another test – 0.02), for the numbers 1 – 0.70, for the numbers 50 – 0.80 (in another test – 0.11), for the numbers 100 – 0.58, for the numbers 150 – 0.79, for the numbers 200 – 0.64, for the numbers 255 – 0.73 (in another test – 0.10).
Let us take, perhaps, the worst case among those listed above – encrypting the numbers 0 – and run a longer experiment for it: we will try to guess the key 8192 times (32 times more than before). We find that the degree of similarity by the chi-squared criterion equals 0.61, which is a further confirmation of our hypothesis.
Collecting separate statistics on the first bytes of the messages in this same experiment (in the original message this position held the zeroed padding byte), we obtain a degree of similarity between the real and the uniform distributions that is very close to zero (9E-320), showing their strong divergence. A close look at the results speaks for itself (fig. 3). The first byte never took a value in the range [205; 255] over the 8192 iterations, meaning its value is strictly bounded from above. This limitation appears to be an inherent property of the RSA algorithm. The first byte took the value 0 in only 45 of the 8192 iterations, meaning that an attacker aware of the padding scheme used could, in our experiment, already discard (8192-45) / 8192 * 100% ~ 99.45% of the results as untrustworthy at this step alone. However, as already mentioned, in this work we do not take this circumstance into account when collecting statistics. It is worth mentioning that in this experiment we obtain only 8192 distinct first bytes, and with a uniform distribution each possible value from 0 to 255 would correspond to only 32 occurrences, which is a rather small number for statistics. Unfortunately, running longer (and, correspondingly, more reliable) experiments is difficult for us.
Fig. 3. Distribution of the message's first byte. Blue shows the real distribution, red – the uniform one
To sum up, if we had the opportunity to run a greater number of large-scale experiments within a reasonable amount of time, we might obtain a closer match. On the other hand, experience shows that some encryption keys cause the “plaintext larger than the modulus” error to appear considerably more often during decryption than others: this error either never appears at all during a program run, or appears rarely, or appears often. There is a hypothesis that this, too, may affect the statistical properties of the decryption results.
Thus, even taking into account the noticeable spread of the values, the assumption that data decrypted with the wrong key is pseudorandom is, on the whole, correct, as confirmed by the charts built from the data obtained. The distribution is not strictly uniform, but is close to it.
3. Sketches for a mathematical treatment of the question
Of course, it would be ideal to prove the uniformity of the distribution under decryption with the wrong key not only computationally, but also strictly mathematically. Unfortunately, this is a very difficult question that lies beyond the author's competence. Confirmation of this difficulty can be found, for example, in a paper by French researchers [16], who examine considerably narrower questions and nevertheless find the difficulty to be very high.
Nevertheless, we would like to present some sketches that may be useful for future work on this topic. A program [18] was written, with the help of which some conclusions can be drawn about the distribution of the results of the expression x^y mod p, where y>=2, with p and y fixed in each experiment. The point is that if, under the conditions described above, the results of this expression do not repeat for all x in the interval [0; p-1], then the distribution of results will be uniform; conversely, even a single repetition will make the distribution non-uniform.
Let us run the following experiment: p lies in the interval [2; 100]; y lies in the interval [2; 40]; x lies in the interval [0; p-1], running through all its possible values in each experiment. We obtain the following results:
1. If p = 2, then for any power y from the interval [1; 40] we get a uniform distribution. It's simple: 0^y mod 2 = 0 for any power y>=1, 1^y mod 2 = 1 for any power y>=1, so the distribution will be uniform here for any y>=1.
2. If p = 3, then for any odd power y from the interval [1; 40] we get a uniform distribution. This is because 0^y mod 3 = 0 for any power y>=1, 1^y mod 3 = 1 for any power y>=1, while 2^y mod 3 = 2 only for odd powers y, so the distribution will be uniform here for any odd y>=1.
3. If p takes a value from the set {4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28, 32, 36, 40, 44, 45, 48, 49, 50, 52, 54, 56, 60, 63, 64, 68, 72, 75, 76, 80, 81, 84, 88, 90, 92, 96, 98, 99, 100}, then a uniform distribution does not occur even once for any y from the interval [2; 500]. It is easy to notice the pattern – all these numbers are multiples of at least one of the following numbers: 4 (2^2), 9 (3^2), 25 (5^2) and 49 (7^2), that is, squares of prime numbers. Apparently, this pattern continues to hold beyond this range.
4. If p does not satisfy the condition described above of being a multiple of the square of a prime number, then there necessarily exists a set of odd values of y for which the distribution will be uniform. For example, if p = 29, then in our experiment y can belong to the set {1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27, 29, 31, 33, 37, 39}. Here a pattern can be seen if we find the differences between neighbouring terms: 3-1 = 2, 5-3 = 2, 9-5 = 4, 11-9 = 2, 13-11 = 2, 15-13 = 2, 17-15 = 2, 19-17 = 2, 23-19 = 4, 25-23 = 2, 27-25 = 2, 29-27 = 2, 31-29 = 2, 33-31 = 2, 37-33 = 4, 39-37 = 2. First the difference equals 2 twice, then it equals 4; then it equals 2 five times, then it equals 4; then it equals 2 five times, then it equals 4. The situation is similar for other suitable values of p – for them too, y can belong to a set of values connected by some rule. Apparently, the patterns mentioned above continue to hold beyond this range as well.
In the RSA algorithm, during decryption the role of the modulus p from the constructions above is played by the number n = p*q, where p and q – are prime numbers; the role of the power y is played by the secret exponent d, and the role of x is played by the ciphertext x from the interval [0; n-1]. The RSA standard states that p !=q: “In a valid RSA public key, the RSA modulus n is a product of u distinct odd primes”. It follows directly from this that we are dealing with situation 4 considered above (since the modulus is equal to a product of distinct prime numbers, it cannot be a multiple of the square of any prime number). Since d = e^(-1) mod φ(n) = e^(-1) mod (p-1)*(q-1), d is most likely able to be any number (actually, this requires further investigation!), and accordingly the distribution of the decryption results of different messages under one key can be either uniform or non-uniform (correspondingly, in the general case it will be non-uniform).
What interests us far more, however, is the distribution of the results of decrypting a single message with different keys: we would like to consider the situation where, in the expression x^y mod p, the value of y varies over the range [0; p-1], while x and p remain constant throughout each experiment. Reworking the previously described program [18] for this purpose and considering numbers in the interval [2; 50], we find that in a number of cases (though far from always!) the distribution is indeed very close to uniform. In cases where p is a prime number (in our experiments these were the numbers 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47), for certain values of x the result of the expression is uniformly distributed among the values [1; p-1] for powers y in the interval [0; p-2]. In other words, in these cases, for powers y in the interval [0; p-2] the result never takes the value zero, but takes every other possible value exactly once, so the distribution is practically uniform. We were unable to find a pattern in the suitable values of x: for example, for p = 23 the suitable x belong to the set {5, 7, 10, 11, 14, 15, 17, 19, 20, 21}. All that can be said is that there are comparatively quite a few of them — in our experiment, from a quarter to a half of all possible values of x. It is worth noting that such numbers x should not be regarded as primitive roots modulo p [17], since in the general case they are not.
However, in the RSA algorithm, semiprime numbers (products of two prime numbers) are used as moduli, not primes, so, judging by our experiments, such favourable situations will not arise, and therefore, strictly speaking, the distribution cannot be called uniform.
Comments