Could anybody explain me how does a "bit flipping" attack work?

Question

Hi,

I'm auditing a custom web application for a customer, concretely the crypto part of it. I've managed to get some encrypted data in transit from a client browser to the webserver. Since I know the format of the cleartext (it's documented) a colleague suggested that we could try a "bit flipping" attack.

I've read about it online but I don't quite grasp it.

Could anybody please explain it to me (with as little algebra as possible? ;))

 

Thanks in advance!

Rey Misterio

Answer 1

A "Bit Flipping" attack consists of finding out how messages are encrypted and this way be able to forge packets.

This will usually not lead to a compromised system in regards to gain access to it directly but would enable you to send correctly encrypted messages to a receiver.

You would now go on and try to find out which key is used to encrypt the cleartext in order to receive the encrypted message. If you are on a wireless lan you could try to sniff for encrypted packages.

 

Hope that helps.

Answer 2

Hi everyone,

first of all "It's NOT lupus".

About the bit flipping attack, this is rather abstract stuff so it'll be better to use an example. Let's say you have an AES256 encrypted message, I don't know, you sniffed the wireless network, etc.

From the documentation you know the original format of it, for example XXXXYYYYZZZZ, where XXXX is a name, YYYY a digital signature and ZZZZ an amount of money. This knowledge is important because you now know that in order to change the amount you just need to change *precisely those bits*. Let's say the bit number N (which is likely to affect the amount the most, "the first of the first Z").

Most of the "symmetric key" encryption algorithms are based on a series of steps which modify the cleartext bytes as a function of the key. Some of these transformations are simple as translations, cyclic rotations, etc. most like a Rubik's cube. Other's involve some arythmetic but for performance reasons limited to XORs (booo!) XORs are cool because you don't know the key but you do know, at that particular byte it's either a zero or a one ;)

This way, since translation, cyclic rotations and XORs are symmetric operations you can modify the cleartext and follow the process to find which bits are altered in the encrypted text. These are the bytes you want to play with in order to modify the meaning of the cleartext when decrypted by your victim.

Too complicated? It does get worse ;)

This would be rather easy to follow but most of the encryption algorithms have a step designed to produce "dispersion". For example, AES implements a matrix multiplication (luckily a constant matrix). The effect of this is that every bit of the resulting column depends on every bit of the original one. Well, they don't call it "dispersion" for nothing...

Anyway, the idea remains the same, you can drastically reduce the number of bytes you need to change in order to alter the encrypted text and produce a change on the desired bit once decrypted on the victim's side.

 

I hope all this mumble makes sense. It does to me, but is maybe the effect of the pills ;)