Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for information security professionals. It's 100% free, no registration required.

I found this reference to bypass canaries: http://sota.gen.nz/hawkes_openbsd.pdf

It recommends to brute force the canary byte-for-byte. I don't understand how this works: "Technique is to brute force each byte of the canary individually along with time analysis". How can you do time analysis on a byte-for-byte basis? Isn't the whole canary compared at once? I thought that the the four bytes were compared with only one instruction.

This attack is also referenced in http://www.phrack.org/issues.html?issue=67&id=13

share|improve this question

2 Answers 2

up vote 4 down vote accepted

The idea is to control the length of your attack so you only overwrite the first byte of the canary. You can then brute force the 256 possible values for this byte, and using some kind of side-channel figure out which is correct. Once you've got this, you can brute force the second byte, and continue until you've got the whole canary.

share|improve this answer

This topic was likewise confusing me. There's only one or two sentences in that Phrack issue that even mention intelligently controlling the length of the buffer overrun (probably because this is a typical technique). Paj28 appears to have the right answer, but it's still a little vague as to how one would acquire an accurate enough side-channel to make this work in practice. If a large number of attempts are required in order to do statistical analysis, this is clearly going to reduce the effectiveness of the attack (especially in the remote case where a new network connection and a fork() syscall occur for every attempt).

Common SSP methods use a single canary which is copied to the stack from a program-wide variable stored in a protected section. This initialization happens during executable load. Three known variants of this initialization are (a) by the kernel during the exec*() syscall, (b) by a piece of startup code for statically-linked executables, or (c) by the dynamic loader's code fragment that is inserted into a dynamically-linked executables' runtime image.

Most importantly, this byte-for-byte trick can be defeated. Consider the following:

{01} Instead of allocating space for one 64-bit word, we can leave two word-length spaces in the stack frame. One such variable slot is placed before the buffers where an overflow is unlikely to be able to modify it.

{02} Upon executing the function prologue, instead of copying a fixed canary to these two slots, we actually derive a dynamic canary from two values (which themselves may be made dynamic to some degree). Most likely our source values would be taken from a block of pre-initialized random protected memory, similar to how the old canaries were established.

{03} The derivation method could be made arbitrarily strong, even cryptographic, but it doesn't need to be for this technique to work.

{04} A simple strategy can make the attacker's life very difficult. Suppose the derivation method is merely something such as A + B = C, where A and B are pseudo-random 64-bit values. C, the check value, would likewise be 64-bit.

{05} Now, when the attacker goes to overwrite the canary, they can only reach B. A survives on the stack untouched due to existing at a lower virtual address.

{06} A + B != C, so obviously the canary check fails as we expect.

{07} However, what has the attack learned from overwriting the first byte of B? Only that A + B doesn't equal C, naturally. As the attack has no information available about what A and C actually are, this creates a large number of possible values for B.

{08} It is not feasible under this scheme to naively sub-divide the word values into bytes and attack them all separately. Due to the nature of modular (wrapping) arithmetic, A[0] + B[0] = C[0] does NOT guarantee that A + B = C. Bits from lower bytes can carry into higher bytes, and bits from the higher bytes can overflow into lower bytes. It's still likely that the attacker will be able to figure out what the first byte of B should be, but it gets drastically harder with each subsequent byte.

{09} Supposing that one finds a means of feasibly defeating this three 64-bit word example in reasonable time, the concept extends arbitrarily to larger numbers of variables and function derivation methods more sophisticated than modular arithmetic. It seems practically self-evident that there is a scheme that is both fast enough for real-world use and sufficiently secure to deter nearly all plausible attacks.

{10} The technique can be further improved if we reserve and secure some memory region for storing the canary inputs. Only one of the canary calculation values actually needs to appear on the stack in order to detect the buffer overrun. All others can exist elsewhere, thus preventing them from being easily read even if the attacker managed to overrun the stack during a different function execution context.

It is very unlikely that I am the first person to realize there are significant improvements than can be made to the stack-smashing protection scheme to defend against this and similar attacks. I merely present this as a trivial proof-of-concept, "just in case".

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.