244 5. Implementation Issues

The first assignment of Q1 is Q1 ← P; if P = (x, y) in affine coordinates, then Q1 = (x : y : 1) in Jacobian coordinates. After this first assignment, the coordinates of Q1 are randomized to (λ2 x, λ3 y, λ), where λ is a randomly selected nonzero element in Fq , and the algorithm proceeds as before. The DPA attack described above is thwarted because the adversary is unable to predict any specific bit of 4Pi (or other multiples of Pi ) in randomized Jacobian coordinates.

5.3.2Electromagnetic analysis attacks

The flow of current through a CMOS device also induces electromagnetic (EM) emanations. The EM signals can be collected by placing a sensor close to the device. As with power analysis attacks, one can now analyze the EM signals in the hope that they reveal information about the instructions being executed and contents of data registers. Simple ElectroMagnetic Analysis (SEMA) attacks and Differential ElectroMagnetic Analysis (DEMA) attacks, analogues of SPA and DPA attacks, can be launched. As with power analysis attacks, these electromagnetic analysis (EMA) attacks are non-intrusive and can be performed with relatively inexpensive equipment.

Since EM emanations may depend on the physical characteristics of the active gates, a single EM sensor captures multiple EM signals of different types. These signals can be separated and analyzed individually. This is unlike the case of power analysis attacks where the power consumption measured is the single aggregation of power consumed by all active units. Consequently, EMA attacks can potentially reveal more information than power analysis attacks, and therefore constitute a more significant threat.

The most comprehensive study on EMA attacks was undertaken in 2002 by IBM researchers Agrawal, Archambeault, Rao and Rohatgi, who conducted experiments on several smart cards and a server containing an SSL accelerator. Their experiments provide convincing evidence that the output of a single wideband EM sensor consists of multiple EM signals, each of which can encode somewhat different information about the device’s state. Moreover, they succeeded in using EMA attacks to compromise the security of some commercially available cryptographic devices that had built-in countermeasures for resisting power analysis attacks, thus demonstrating that EMA attacks can indeed be more powerful than power analysis attacks.

As with power analysis, EMA countermeasures could be hardware based (e.g., metal layers to contain the EM emanations or circuit redesign to reduce the EM emanations) or software based (e.g., use of randomization). The study of EMA attacks is relatively new, and it remains to be seen which countermeasures prove to be the most effective.

5.3.3Error message analysis

Another side channel that may be available to an adversary is the list of error messages generated by the victim’s cryptographic device. Consider, for example, the decryption

5.3. Secure implementation

245

process of a public-key encryption scheme such as ECIES (see §4.5.1). A ciphertext might be rejected as invalid because some data item encountered during decryption is not of requisite form. In the case of ECIES decryption (Algorithm 4.43), a ciphertext (R, C, t) will be rejected if embedded public key validation of R fails, or if Z = hd R = ∞, or if the authentication tag t is invalid. There are several ways in which the adversary may learn the reason for rejection. For example, the error message may be released by the protocol that used the encryption scheme, the adversary may be able to access the error log file, or the adversary may be able to accurately time the decryption process thereby learning the precise point of failure. An adversary who learns the reason for rejection may be able to use this information to its advantage.

To illustrate this kind of side-channel attack, we consider Manger’s attack on the RSA-OAEP encryption scheme. Manger’s attack is very effective, despite the fact that RSA-OAEP has been proven secure (in the random oracle model). This supports the contention that a cryptographic scheme that is secure in a traditional security model is not necessarily secure when deployed in a real-world setting.

RSA-OAEP encryption scheme

RSA-OAEP is intended for the secure transport of short messages such as symmetric session keys. It first formats the plaintext message using Optimal Asymmetric Encryption Padding (OAEP), and then encrypts the formatted message using the basic RSA function. RSA-OAEP has been proven secure (in the sense of Definition 4.41) under the assumption that the problem of finding eth roots modulo n is intractable, and that the hash functions employed are random functions. The following notation is used in the descriptions of the encryption and decryption procedures.

1.A’s RSA public key is (n, e), and d is A’s corresponding private key. The integer n is k bytes in length. For example, if n is a 1024-bit modulus, then k = 128.

2.H is a hash function with l-byte outputs. For example, H may be SHA-1 in which case l = 20.

3.P consists of some encoding parameters.

4.padding consists of a string of 00 bytes (possibly empty) followed by a 01 byte.

5.G is a mask generating function. It takes as input a byte string s and an output

length t, and generates a (pseudorandom) byte string of length t bytes. In practice, G(s, t) may be defined by concatenating successive hash values H (s i), for 0 ≤ i ≤ t/ l − 1, and deleting any rightmost bytes if necessary.

The concatenation m of maskedS and maskedPM is a byte string of length k − 1. This ensures that the integer representation m of m is less than the modulus n which is k bytes in length, and hence m can be recovered from c.

246 5. Implementation Issues

Algorithm 5.8 RSA-OAEP encryption

INPUT: RSA public key (n, e), message M of length at most k − 2 − 2l bytes. OUTPUT: Ciphertext c.

1.Select a random seed S of length l bytes.

2.Apply the OAEP encoding operation, depicted in Figure 5.15, with inputs S, P and M to obtain an integer m:

2.1 Form the padded message PM of length k − l − 1 bytes by concatenating H ( P), a padding string of the appropriate length, and M.

2.2Compute maskedPM = PM G(S, k − l − 1).

2.3Compute maskedS = S G(maskedPM, l).

2.4Concatenate the strings maskedS and maskedPM and convert the result m to an integer m.

3.Compute c = me mod n.

4.Return(c).

P

H

H(P)	padding	M
S	PM

G

G

		maskedS		maskedPM
m=

Figure 5.15. OAEP encoding function.

5.3. Secure implementation

247

Algorithm 5.9 RSA-OAEP decryption

INPUT: RSA public key (n, e), private key d, ciphertext c.

OUTPUT: Plaintext M or rejection of the ciphertext.

1.Check that c [0, n − 1]; if not then return(“Reject the ciphertext”).

2.Compute m = cd mod n.

3.Convert m to a byte string m of length k. Let X denote the first byte of m.

4.If X = 00 then return(“Reject the ciphertext”).

5.Apply the OAEP decoding operation, depicted in Figure 5.16 with inputs P, m:

5.1Parse m to obtain X, a byte string maskedS of length l, and a byte string maskedPM of length k − l − 1.

5.2Compute S = maskedS G(maskedPM, l).

5.3Compute PM = maskedPM G(S, k − l − 1).

5.4Separate PM into a byte string Q consisting of the first l bytes of PM, a (possibly empty) byte string PS consisting of all consecutive zero bytes following Q, a byte T , and a byte string M.

5.5If T = 01 then return(“Reject the ciphertext”).

5.6If Q = H ( P) then return(“Reject the ciphertext”).

6.Return(M).

m= X maskedS

maskedPM

G

G

PM

Q

000000

T

M

Figure 5.16. OAEP decoding function.

Manger’s attack and countermeasures

A ciphertext c [0, n − 1] may be invalid for several reasons: either X = 00 in step 4 of Algorithm 5.9, or T = 01 in step 5.5, or Q = H ( P) in step 5.6. Manger’s attack assumes that an adversary is able to ascertain whether X = 00 in the case that c is found