Proving bit flipping attack on RC4 stream cipher (if weakly implemented)

Hi Guys! in this article we will somehow go to the world of cryptography wherein the hackers play a hide and seek or cat and mouse with the cryptographers. The cryptographers develop encryption to secure information...now hackers break it.....steal something. The technology users caught in between believing that their private files is secure.....only to realize that hackers has stolen their private digital belongings ranging from as simple as picture of the lady you fantasize..... to as serious as bank account......etc. Anyway, in here I just show you a simple way to demonstrate bit flipping on stream cipher. This is changing part of an stream cipher encrypted message without knowing the key. I will be using RC4 which is a popular stream cipher. Then using VBA on the programming side to show you guys how to change encrypted message content.


Stream Cipher is a symmetric key cipher wherein a plaintext (message) is combined with a pseudorandom generated key(KEY) using XOR function. This is like XORing a text we human can read with a somehow unreadable characters which we call the key to produce a result that is also unreadable and looks like alien letters. Symmetric cipher means to decrypt the "unreadable" message you need to know the key that encrypt it. XORing the correct key will reveals the original plaintext message. This means that....or coarse only friends MUST know the key.....NEVER to tell the enemy of the key as this is the one that protects the message.

In everyday life, this is like equating to you and your friends which has "code names" to say the beautiful ladies in your village. Once you say the code name....your friends know who are you talking about but a stranger who happen to hear your conversation might not understand your topic unless he/she too knows the code name. The code name is synonymous with the key.

RC4

RC4 is a popular stream cipher. It generates pseudorandom stream of bits -which will be the key. Then as a stream cipher it will combine with a plaintext message using XOR function to form the encrypted message. To recover the plaintext message, the key is XORed to the encrypted message in reverse.

RC4 concentrates more on generating the key (denoted by "K" on diagram below) which has 2 parts:

1.) Permutation of all 256 possible bytes. Denoted by "S" on diagram.
2.) 2 8bits index pointers. This is indicated by "i" and "j" on the diagram.

in a diagram:

Anyway, on the internet it is not difficult to find VBA function to do the RC4 encryption:

=======================================================================
Public Function RC4(ByVal Expression As String, ByVal password As String) As String

On Error Resume Next
Dim RB(0 To 255) As Integer, X As Long, Y As Long, Z As Long, Key() As Byte, ByteArray() As Byte, Temp As Byte
If Len(password) = 0 Then
    Exit Function
End If
If Len(Expression) = 0 Then
    Exit Function
End If
If Len(password) > 256 Then
    Key() = StrConv(Left$(password, 256), vbFromUnicode)
Else
    Key() = StrConv(password, vbFromUnicode)
End If
For X = 0 To 255
    RB(X) = X
Next X
X = 0
Y = 0
Z = 0
For X = 0 To 255
    Y = (Y + RB(X) + Key(X Mod Len(password))) Mod 256
    Temp = RB(X)
    RB(X) = RB(Y)
    RB(Y) = Temp
Next X
X = 0
Y = 0
Z = 0
ByteArray() = StrConv(Expression, vbFromUnicode)
For X = 0 To Len(Expression)
    Y = (Y + 1) Mod 256
    Z = (Z + RB(Y)) Mod 256
    Temp = RB(Y)
    RB(Y) = RB(Z)
    RB(Z) = Temp
    ByteArray(X) = ByteArray(X) Xor (RB((RB(Y) + RB(Z)) Mod 256))
Next X
RC4 = StrConv(ByteArray, vbUnicode)
End Function
========================================================================

The function above is now simple. You only need to supply arguments which are: "Expression" which is the plaintext message then with "password " which is the encryption word.

Example:

To encrypt:
Dim encrypt1 As String
encrypt1 = RC4("For_encryption_message", "This_is_the_key")
MsgBox encrypt1

The output is an alien like letter...hieroglyphs.....call it whatever you like :-)

To decypt:
Dim encrypt1 As String
Dim decrypted As String
encrypt1 = RC4("For_encryption_message", "This_is_the_key")
'======To decrypt...simple do the reverse===========
decrypted = RC4(encrypt1, "This_is_the_key")
MsgBox encrypt1 & "     when encrypted    " & "the decrypted message is...." & decrypted

 

 

 

 

Vulnerabilities of Stream Ciphers

 

Both the two vulnerabilities of stream cipher exploits the commutative law of XOR function:

 

1.) Reused key attack

 

Say "K" is the key, "A" is the plaintext message1 and "B" another plaintext message2

 

K ^ A  - will be the key and the plaintext message1 XORed.

K ^ B  - will be the key and the plaintext message2 XORed.

 

now if these two are XORed together

 

   (K ^ A) ^ (K ^ B)

=A^B

 

Due to commutative property of XOR, the "K" will be cancelled which means the effect of the "K" -the key has been eliminated.

 

This means that on reused key attack. If two message is encrypted using same key, XORing their encypted message will remove the effect of the key. If say, you know "plaintext message2" then you will know  "plaintext message1" as XORing it further:

 

=A^B ^B

=A

 

2.) Bit flipping

 

This is my topic in this blog :-)

 

Say in an encrypted message, I know that it contain "this" word. I can change "this" to say "that" by:

 

(K ^ "this") ^ "this" ^ "that"

=K ^ "that"

 

Again, due to commutative property of XOR, the "this" will be cancelled and changed to "that" even without knowing the key "K".

 

 

 

Proving the Bit Flipping

 

Now guys I will prove to you the bit flipping.

 

Let say I have a string "Try_bit_flip" encrypted to RC4 using password "This_is_the_key"

 

so in VBA:

 

Key = "This_is_the_key"

Encrypted = RC4("Try_bit_flip", Key)

 

so "Encrypted " contain now the encrypted message. Suppose that I know that the message contains "Try_bit" and I want to change it to "TRYTHIS"

 

so the expression will be:

 

(K ^ "Try_bit_flip") ^ ( ("Try_bit" ^ "TRYTHIS") + added_zero_to_equal_length)

=K ^ "TRYTHIS_flip"

 

take note that we need to add zero on the end when XORing "Try_bit" and "TRYTHIS" because they are not same length as with the string "Try_bit_flip". The zero will leave the other characters undisturbed. Anyway, here's the complete code:

 

===============================================================

 

Sub Bit_flipping_attack_on_RC4()
Dim Encrypted As String
Dim Key As String
Dim ExhangeString As String
Dim bitflip As String
Dim OverallMessageString As String

Dim ByteArraycrypted() As Byte
Dim ByteFlip() As Byte
Dim ExchangeString() As Byte

Dim ByteArrayFlipExhange() As Byte
Dim OverallEncrypted() As Byte

Key = "This_is_the_key"

Encrypted = RC4("Try_bit_flip", Key)

bitflip = "Try_bit"
ExhangeString = "TRYTHIS"

ReDim ByteArraycrypted(Len(Encrypted)) As Byte
ReDim OverallEncrypted(Len(Encrypted) - 1) As Byte
ReDim ByteFlip(Len(bitflip)) As Byte
ReDim ExchangeString(Len(ExhangeString)) As Byte
ReDim ByteArrayFlipExhange(Len(Encrypted)) As Byte

ByteArraycrypted() = StrConv(Encrypted, vbFromUnicode)
ByteFlip() = StrConv(bitflip, vbFromUnicode)
ExchangeString() = StrConv(ExhangeString, vbFromUnicode)

 

'===============XOR the known string on the encrypted word and the word to put in exhange===============
For i = 0 To (Len(bitflip) - 1)
    ByteArrayFlipExhange(i) = (ByteFlip(i)) Xor (ExchangeString(i))
Next i

'================ADD zero on the end as not to effect the other content of the message============
For i = Len(bitflip) To (Len(Encrypted) - 1)
    ByteArrayFlipExhange(i) = 0
Next i

'==============Now xor to the encrypted string===============
For i = 0 To (Len(Encrypted) - 1)
    OverallEncrypted(i) = ByteArraycrypted(i) Xor ByteArrayFlipExhange(i)
Next i

'======COnvert back byte to string==============
OverallMessageString = StrConv(OverallEncrypted, vbUnicode)

'=====Now Decrypt the message -the other parts will show it was modified============
MsgBox Trim(RC4(OverallMessageString, Key))
End Sub

 

 

===============================================================

 

 

Sure, running the code. When the message is decrypted using the original password (Key = "This_is_the_key") it doesn't contain "Try_bit_flip" but :

 

which is change without knowing the password or key.

 

 

Anyway, have a nice time guys. Thanks for reading!!