Protecting Ed448 against DPA and fault attacks

Question

There are some papers (1, 2) describing fault attacks in EdDSA. One suggested countermeasure is to add randomness to the input of the first hash call, which outputs a scalar.

This paper describes a DPA attack against EdDSA, and suggests a similar countermeasure. However, the randomness must be placed in a specific place:

This can be achieved by padding the key with fresh random bits such that the first 1024-bit block is composed only by key and random value, without any bits known to the attacker.

Following their notation, that would mean changing $H(b,M)$ to $H(b,Z,M)$ where $Z$ is the random padding such that the length of $b || Z$ is equal to the block size of the hash.

However, consider Ed448, as defined in RFC 8032 (the issue I'll talk about would also apply to Ed25519ctx and Ed25519ph, but I'll use Ed448 as an example). In the Sign operation, the hash call is SHAKE256(dom4(prehash, context) || b || PH(M), 114). Prehash is a flag indicating Ed448 or Ed448ph. Context is an optional context string. The dom4 function is:

dom4(x, y): The octet string "SigEd448" || octet(x) || octet(OLEN(y)) || y, where x is in range 0-255 and y is an octet string of at most 255 octets. "SigEd448" is in ASCII (8 octets).

Now, my question is: what is the proper way to add the DPA countermeasure to Ed448? (And Ed448ph, Ed25519ph, Ed25519ctx)?

My first guess would be to use SHAKE256(dom4(prehash, context) || b || Z || PH(M), 114), with Z being enough bytes to fill the SHAKE245 block size. However, if the context is used, then Z could get too small. Also, the paper states that the first block must be "composed only by key and random value, without any bits known to the attacker". Would the fixed bytes of the dom4 function ("SigEd448" and so on) interfere with this? How to work around this?

Or maybe SHAKE256 is already DPA-resistant?

Answer 1

The, common, assumption used in that paper is that an attacker can DPA a fixed secret when it's mixed with known (to the attacker) and varying data.

The proposed solution was to add random after the key to fill the SHA-512 block size.

By doing this:

1. the first SHA-512 computation processes the fixed secret and varying but unknown data, so the attacker can't perform DPA.
2. After the first block, the result is the intermediate hash value which is unknown and varying (from message to message), so it can't be recovered through DPA when processing subsequent blocks.

Side note: if we would have padded the key with zeros instead of random, we would have mixed the fixed key with known but fixed data. The attacker in this case is not able to DPA the key. However she can DPA the intermediate hash value after the first block, which is secret and now fixed and will get mixed with the known and varying message.

Your proposed solution SHAKE256(dom4(prehash, context) || b || Z || PH(M), 114) with Z random data would work if you carefully select the size of Z and assuming the attacker can't control the context.

If the attacker control the context then she can choose varying context that together will the key (b) will completely fill the SHAKE256 block, so no random is used in that computation and DPA can be performed.

If the attacker can't control the context then you just have to make sure that Z is not too small and fills the block.

For example, given the block size of SHAKE256 of 136 bytes, if len(dom4(prehash, context) || b)=134, due to a large context, then 2 bytes for Z won't be enough and you will need to select a Z of 138 bytes (2 to fill the current block and 136 for another full block).

---

Update: Please be aware that the generation of r is one way to side-channel attack EdDSA, but it's not the only one. The scalar multiplication should be protected as well from single trace attacks (technically not DPA) and the computation of $S = (r + k * s)$ could be targeted by DPA as $s$ is fixed and unknown and $k$ is varying and known.