Fault attacks can be divided into two classes: hardware fault induction attacks and software fault attacks. The former class refers to all attacks that involve the manipulation of hardware during a cryptographic computation, employing lasers, electromagnetic pulses, extreme temperatures, or voltage glitches with the purpose of disturbing the computation and provoke the output of data that is useful to the attacker. In contrast, software fault attacks simply exploit the realisation of error handling within processing routines. They are conducted by feeding specially crafted input into a device and monitoring its response, often with large number of iterations. Such attacks can exploit error messages that are too informative about the reason of an internal failure, e.g. Bleichenbacher's attack on PKCS#1 v1.5, or the lack of input data validation, e.g. the input of invalid points in Elliptic Curve Diffie-Hellmann.

Here I want to investigate the feasibility of a new class of software fault attacks: memory allocation fault attacks. The idea is very simple: if at a certain point during the computation the cryptographic implementation issues a memory allocation request, e.g. through the malloc function in C, the length of which depends on some secret value in such way, that the attacker gains useful information from that length, then the following attack may be possible: Assume the attacker wants to determine if the attacked value during has length at most l or greater. The attacker brings the system into a state, e.g. by causing memory allocations with sizes of his choice by interacting with the system, so that subsequently the largest possible further allocation is l. Then he inputs a value of his choice and monitors the system's response. If the computation finishes normally, he concludes that the value of interest had a size of at most l. If the device outputs an error, he concludes that this is due to a memory-allocation failure and thus that the attacked value had a size greater than l. Furthermore, the memory allocation failure might result in an explicit error reply or log message.

This is certainly a rather simplified description of the attack. Generally, in any real implementation of the attacked algorithm other memory allocations will be performed prior to the attacked allocation. In that case, the attack will still work if the total size of these allocations is constant with high probability. There are further details that have to be considered: The heap implementation might not handle the allocation requests with byte-granularity. This means that for instance on a 32-bit system, due to the platform's 32-bit alignment requirement, an allocation request for x bytes might already fail if x rounded up to the next multiple of four is larger than l.

However, this requirement can be dropped if an attackable memory allocation is performed within a conditional branch, where the condition is a secret value. Code with this property will in general be a much more suitable target for this type of attack.

Furthermore, one crucial requirement for the attack to work is that the attacker can determine whether the memory allocation failure that occurred was really caused by the allocation of the value he wishes to attack or by a subsequent allocation. There are two possibilities how this can be ensured. The first one is given when the attacked allocation is performed at the peak heap usage during that cryptographic operation. In that case, and given that the previous allocation sizes during that operation are constant and known to the attacker, he will indeed be able to mount this distinguishing attack. The second possibility is given when there are subsequent allocations performed during the routine that increase the total heap usage, but the attacker can distinguish them from the allocation of interest through the timing of the error reply. A similar case is Manger's attack, which also re-enables a fault attack by distinguishing fault conditions with otherwise indistinguishable error replies through the timing.

Manger's attack would also be a possible candidate for the memory allocation fault attacks. The original attack determines whether the leading byte of the RSA decryption result in OAEP decoding is zero or not. Manger presented his attack either as a fault attack, which is enabled when a specific validity check on the leading byte outputs an explicit error message, or as a timing attack, when the error message is not revealing the failure of this check, but the above error condition can be distinguished from other causes by the timing of the operation. In order to be vulnerable to memory allocation fault attacks, an implementation of the RSA-OAEP decryption would have to allocate one byte fewer when the leading byte is zero at a certain point during the OAEP decoding, e.g. when copying that value, where this difference of one byte leads to a failure in the memory allocation for the longer request while the shorter request can be satisfied. Furthermore, the peak heap usage would have to be reached during OAEP decoding, which could be true if the memory used during the RSA decryption remains allocated in some context object, intended to be reused in the next decryption.

Obviously, there is a large number of "ifs" in the description, making it rather unlikely to find a vulnerable implementation like this. The point of this discussion is merely to arouse awareness to this potential class of fault attacks. If code is vulnerable to them, unexploitable timing vulnerabilities resulting from small differences in allocated sizes and conditional branching might be leveraged to exploitable fault attacks.