Chapter 5

Cryptocounters

A common trigger used in viruses to decide when to attack is a counter value. Such viruses typically do not trigger until it has propagated itself a certain minimum number of times. The Den Zuk virus contains such a trigger [289]. When counters are used only to measure the number of viruses in the wild, a good approach is to utilize two different generation counters. One counter would store the generation number of the virus that is incremented by one in each child a given virus has. This would provide the height h of the family tree. The other counter would be used to measure the average number of children that each virus has (see Chapter 1). This mechanism could be used as a tool for measuring replication performance of viruses in real-world infections.

However, antiviral analysts would likely benefit more than virus writers from the incorporation of counters in virus code since they would receive better population samplings. To solve this malware problem, a method is needed to implement such counters in a way that the viruses can increment the counters but that only the virus writer can read the actual counter values. A cryptocounter is a cryptographic primitive that solves this problem.

In this chapter a simple cryptocounter scheme is presented based on the ElGamal public key cryptosystem. Drawbacks to this approach are then given, followed by an improved approach based on the Paillier public key cryptosystem. The chapter concludes with discussion of even more ways to implement a cryptocounter.

5.1 Overview of Cryptocounters

Informally, a cryptocounter is a probabilistic public key encryption that encrypts a counter value that anyone can increment or decrement but that can only be decrypted using the appropriate private key. Put another way, it is a malleable ciphertext that allows the plaintext to have 1 added to it or 1 subtracted from it. The increment and decrement operations can be performed by anyone without even knowing the plaintext value and without first decrypting the encryption of the counter value.

The typical threat model for the operation of a cryptocounter is the honest-but-curious model. In this model, it is assumed that the machine that increments the cryptocounter does so properly, and does not change the counter in unexpected ways. For instance, if the algorithm normally increments the cryptocounter once every hour, the machine does not maliciously increment it twice every hour, and so on. It is assumed that the machine that operates on the cryptocounter ciphertext is passive and merely observes any and all computations regarding the counter. The machine may do its best to try to learn the counter value based on these observations, hence the term curious. In this sense the machine is a form of passive adversary. But, the machine does not interfere with the normal operation of the counter, which is a capability that active adversaries have.

By placing a cryptocounter within the virus, there is an added level of protection over the use of a plaintext counter. The counter value that the cryptocounter encrypts will never be revealed. This holds even if snapshots of the cryptocounter are taken on a regular basis. Such snapshots can occur as the result of coredumps and so forth. It is necessary to monitor the operations on the cryptocounter each step of the way in order to keep track of the current counter value.

Consider a virus that stores two cryptocounters to help keep track of the number of viruses in the wild. It is relatively safe to assume that before the virus is discovered, the host machine will not corrupt the counter value and will not interfere with the virus when it increments the counter. Also, it is prudent to assume that once the virus is found several system administrators may examine their logs to try to determine the counter values. Assuming that the snapshots are spaced out reasonably far enough, the snapshots are not likely to reveal the counter values that the viruses contain.

5.2 Implementing Cryptocounters

In this section two methods for implementing cryptocounters are given. This first is based on the ElGamal public key encryption algorithm. Although conceptually very simple, this approach has a significant drawback when counter values are large. The second approach is almost as simple as the first. It is a counter based on the Paillier public key cryptosystem. The Paillier cryptosystem is described and it is shown how to use Paillier to implement a simple cryptographic counter.

5.2.1 A Simple Counter Based on ElGamal

It is straightforward to utilize the ElGamal public key cryptosystem to implement a rudimentary cryptocounter. In the semantically secure version of ElGamal (see Appendix C.2.2) the message space consists of all messages m such that m^q = 1 mod p. Here q is a large prime that divides p − 1 evenly. Since the cryptosystem is malleable under multiplication modulo p, the plaintext can be multiplied by values modulo p without ruining the decipherability of the ciphertext. So, a simple counter can be implemented using the public key (y, g, p) as follows.

The plaintext is initially set to g¹ = g. By choosing k₁ randomly, the first counter value is computed to be the pair (a₁, b₁) that is equal to (g^k₁ mod p, y^k₁ g mod p). To increment the counter by 1, the ciphertext (a₂, b₂) can be computed by setting (a₂, b₂) = (a₁, b₁ g mod p). Similarly, (a₃, b₃) = (a₂, b₂ g mod p). When this ciphertext is decrypted, the plaintext is found to be g³ mod p. This is illustrated in Table 5.1.

However, there is a problem with this approach since it paves the way for correlation attacks against the virus. For example, consider a generation counter that is incremented by one in each child. Suppose that a virus on machine A has a child on machine B and that this virus has a child on machine C. The ciphertexts on A, B, C would be (a₁, b₁), (a₂, b₂), (a₃, b₃), respectively. Observe that the equalities a₁ = a₂ = a₃ hold. The problem is that b₃/g = b₂ mod p and b₂/g = b₁ mod p. So, the path of the virus can be ascertained based on the relationships between b₁, b₂, and b₃.

This problem can be solved by rerandomizing the ciphertexts each time the counter is incremented. This makes correlation impossible due to the semantic security of the underlying cryptosystem. This approach will now be described. The plaintext is initially set to g¹ = g. By choosing k₁ randomly, the first counter value is computed to be (a₁, b₁) = (g^k₁ mod p, y^k₁ g mod p). To increment the counter by 1, the ciphertext (a₂, b₂) is computed by choosing k₂ < q randomly and setting (a₂, b₂) = (a₁ g^k₂ mod p, b₁y^k₂ g mod p). When this ciphertext is decrypted, the plaintext is found to be g² mod p. To see that this works, note that = g² mod p. To increment the counter again, the ciphertext (a₃, b₃) = (a₂g^k₃ mod p, b₂y^k₃g mod p) is computed using a randomly chosen value k₃ < q, and so on. This is illustrated in Table 5.2. This method stores the actual counter value in the exponent of g. The counter value i therefore corresponds to the ElGamal plaintext gⁱ mod p.

Table 5.1 Flawed ElGamal Cryptocounter

Suppose that the cryptocounter ciphertext (a_i, b_i) is obtained from a virus. By performing ElGamal decryption the plaintext m = b_i/a^x_i mod p is found. Since m = gⁱ mod p, computing i is equivalent to computing the base g discrete logarithm of m. Provided that i is not exponentially large, this can be done by testing whether or not gⁱ = m mod p for i = 1, 2, 3,... until the equality holds.

5.2.2 Drawback to the ElGamal Solution

The drawback to this counter is that there is no trapdoor for the counter value. The value for i must be found by brute-force after gⁱ mod p is computed via decryption. Consider an application in which the counter value is not always incremented by one. If at some point the counter is incremented by an exponentially large value, it will take exponential time to determine the exact counter value during decryption. When used for implementing virus generation counters this drawback may not be very significant, but in other applications it may well be. Cryptographic counters like this one can be used in a variety of ways. They are ideal mechanisms for securely gathering statistics on untrustworthy host machines and are general tools for securing mobile agents.

Table 5.2 ElGamal Cryptocounter

5.2.3 Cryptocounter Based on Squaring

The ElGamal cryptocounter is trivial to decrement by anyone. To decrement (a_i, b_i) one need only compute (a_i, b_ig⁻¹ mod p) and then rerandomize the new pair. This drawback can be heuristically avoided using the following variation of the counter. It is very similar to the ElGamal cryptocounter in terms of choosing exponents randomly, rerandomizing, decrypting the counter, etc. However, instead of using the prime p, the modulus n is used where n is the product of two secret primes. The value g is chosen such that it has order (n)/2. Hence, g is a quadratic residue modulo n.

The counter value 0 is represented by a randomly chosen quadratic residue a modulo n that is kept secret. To increment the counter by 1, both a_i and b_i are squared modulo n. Thus a² corresponds to a counter value of 1, a⁴ mod n corresponds to a counter value of 2, and so on (see Table 5.3).

Just as in the ElGamal cryptocounter there is no trapdoor here. To determine the counter value the pair (a_i, b_i) is decrypted using x and the resulting plaintext is a²ⁱ mod n. The counter value is i and this can be found by brute force. A brute force approach is to start with a, square it repeatedly and stop when a value is found that matches the plaintext of (a_i, b_i).

Consider the problem of decrementing the counter without a and without knowing the factorization of n. This can be trivially accomplished by reverting to a previously stored cryptocounter pair if one is available. If no previous snapshots of the cryptocounter are available, then the counter value can be modified by setting b_i = b_iw mod n where w is a quadratic residue modulo n. However, this modification is not likely to be meaningful since a is kept secret.¹ Decrementing a cryptocounter pair directly without any previous copies amounts to computing a square root of a_i and a square root of b_i modulo n, which is intractable.

Table 5.3 Squaring Cryptocounter

5.2.4 The Paillier Encryption Algorithm

Perhaps one of the simplest and most elegant solutions to the problem of implementing a cryptocounter is to use Paillier's public key cryptosystem [216]. The Paillier cryptosystem constitutes a one-way trapdoor under the computational composite residuosity assumption (see Appendix B.3.3). The Paillier cryptosystem is semantically secure against plaintext attacks under the decision composite residuosity (DCR) problem (see Appendix B.3.4).

The value n in Paillier is the product of two large primes p and q, the same as in RSA. The Paillier cryptosystem is based on the following two properties of Carmichael's function.

1. For any w contained in , the congruence w⁽ⁿ⁾ ≡ 1 mod n holds.
2. For any w contained in , the congruence wⁿ⁽ⁿ⁾ ≡ 1 mod n² holds.

In RSA the public exponent e in the public key (e, n) is relatively prime to (p − 1)(q − 1). Typically, the value e is shared by all the users. Paillier's cryptosystem is quite a bit different since it does not employ e. Instead, the cryptosystem utilizes an integer g that has order v modulo n² with v satisfying the following congruence.²

The value g is shared by all the users. The public key is (n, g) and the private key is (n).

The following is how to encrypt a message m, which is an integer satisfying m < n. A value u is chosen uniformly at random from and the ciphertext c is computed as follows,

The function L(x) = is used for decryption. The following equation shows how to decrypt c to recover m.

It remains to show that decryption succeeds for all messages m. By Euclid's division rule, given positive integers g⁽ⁿ⁾ and n² with n² ≠ 0, there exist unique integers q and r, with 0 ≤ r < n² such that g⁽ⁿ⁾ = qn² + r. In this equation q is the quotient and r is the remainder upon dividing g⁽ⁿ⁾ by n². The value r equals g⁽ⁿ⁾ mod n². By reducing both sides modulo n this implies that,

By property (1),

By transitivity, equations 5.4 and 5.5 imply that r ≡ 1 mod n. Hence, g⁽ⁿ⁾ mod n² is congruent to 1 modulo n. So, there exists an integer β < n such that g⁽ⁿ⁾ mod n² = 1 + βn. Hence,

By subtracting 1 from both sides it follows that g⁽ⁿ⁾ − 1 ≡ βn mod n². This implies that g⁽ⁿ⁾ − 1 mod n² = βn mod n². Define t₁ to be g⁽ⁿ⁾ − 1 mod n². So, t₁ = βn mod n². By applying the division rule again, it follows that there exists a k₁ such that βn = k₁n²+t₁. So, t₁/n = β − k₁n. By reducing both sides modulo n, it follows that t₁/n ≡ β mod n. Since t₁/n = L(g⁽ⁿ⁾ mod n²) this implies that

By raising both sides of equation 5.2 by (n) and reducing modulo n² it follows that c⁽ⁿ⁾ ≡ (g^m uⁿ)⁽ⁿ⁾ mod n². From property (2), the value uⁿ⁽ⁿ⁾ = 1 mod n². Hence,

Now, by substituting equation 5.6 for g⁽ⁿ⁾ in equation 5.8 it follows that c⁽ⁿ⁾ ≡ (1 + βn)^m mod n². The Binomial Theorem describes the expansion of the binomial (1 + βn) on the right side of this equation. But, since this equation is reduced modulo n², every term will be zero except for the first two terms of the expansion. As a result, c⁽ⁿ⁾ = 1 + mβn mod n². So,

But this implies that c⁽ⁿ⁾ − 1 mod n² = mβn mod n². Define t₂ to be c⁽ⁿ⁾ − 1 mod n². By the division rule, there exists a k₂ such that mβn = k₂n² + t₂. Hence, t₂/n = mβ − k₂n. By reducing both sides modulo n it follows that t₂/n = mβ mod n. Since t₂/n = L(c⁽ⁿ⁾ mod n²) this implies that,

By substituting equation 5.7 for β in equation 5.10 it follows that,

Multiplying both sides by L(g⁽ⁿ⁾ mod n²)⁻¹ mod n results in the plaintext m.

Since the quantity L(g⁽ⁿ⁾ mod n²)⁻¹ mod n is always the same each time that a ciphertext c is decrypted, this value can be computed once and for all. So, let ψ = L(g⁽ⁿ⁾ mod n²)⁻¹ mod n. The user can then store ((n),ψ) as his or her private key. Equation 5.12 shows how to decrypt c using ψ.

As in RSA, the Chinese Remainder Theorem can be used to speed up decryption. A variant of Paillier's scheme has been proposed that makes some efficiency improvements regarding the size of Paillier ciphertexts [79].

5.2.5 A Simple Counter Based on Paillier

The way to utilize this cryptosystem as a cryptocounter is straightforward. The counter is initially set to m =1. To encrypt this counter value, u₁ is chosen randomly and the ciphertext is computed to be c₁ = g¹uⁿ₁ mod n². To increment the counter by one, u2 is chosen randomly and the value c₂ = c₁guⁿ₂ mod n² is computed. In general, c_i = c_i−1guⁿ_i mod n². This rerandomization guarantees that each counter value is encrypted in a semantically secure fashion.

The benefit of this approach as opposed to the ElGamal solution is that no comparisons are necessary when c_i is decrypted. The value i is found immediately. A depiction of what a cryptocounter looks like when viewed on an untrusted machine is given on the right side of Figure 5.1.

5.3 Other Approaches to Cryptocounters

The Paillier cryptocounter is efficient in the sense that the counter value can be computed in poly-time even if the counter value is exponentially large. The Paillier cryptosystem constitutes an additive homomorphism under multiplication modulo n² since the product of two ciphertexts yields a ciphertext containing a plaintext that is the sum of the two original plaintexts. A cryptocounter was proposed by Katz et al that does not rely on this property [152]. Their construction shows how to implement a cryptocounter given any encryption scheme that is homomorphic over the additive group ₂. As a result, cryptocounters can be constructed based on the quadratic residuosity assumption.

Figure 5.1 Plaintext counter vs. cryptocounter

In summary, cryptocounters can be implemented based on the Decision Diffie-Hellman problem, the problem of distinguishing n^th residues modulo n², and the composite quadratic residuosity problem. So, if the Decision Diffie-Hellman problem is found to be tractable, for example, then one of the other settings might still provide a secure foundation for this primitive. It is also quite possible that cryptocounters can be synthesized based on other intractability assumptions as well.