浅析FMS attack

本文第一发布平台为安全客：https://www.anquanke.com/post/id/231461

简介

FMS attack是对广泛使用的RC4流密码的攻击，本人将简单介绍一下该攻击。

RC4

RC4（Rivest Cipher 4）是一种流加密算法，密码长度可变，是有线等效加密（WEP）中采用的加密算法。其原理比较简单，包括密钥调度算法（KSA）和伪随机子密码生成算法（PRGA）两大部分：

KSA

RC4初始化的时候会先对state进行初始化，如下所示：

def __init__(self):
	self.state  = [i for i in range(256)]
	self.i      = 0
	self.j      = 0

然后将使用key来对state进行更新，每一步都会将两个状态的值互换：

def __swap_state(self, a, b):
	self.state[a], self.state[b] = self.state[b], self.state[a]
  
def ksa(self, key):
  j = 0
  for i in range(256):
    j = (j + self.state[i] + key[i % len(key)]) % 256
    self.__swap_state(i, j)

PRGA

当要产生密钥流的时候，进行如下操作。在生成密钥流的同时，也会对状态进行实时的更新，以保证其安全性：

def prna(self):
	self.i = (self.i + 1) % 256
	self.j = (self.j + self.state[self.i])  % 256
	self.__swap_state(self.i, self.j)
	return self.state[(self.state[self.i] + self.state[self.j]) % 256]

FMS攻击

FMS（Fluhrer, Mantin and Shamir)）attack是一种针对RC4的攻击，这种攻击方式在2001年的论文Weaknesses in the Key Scheduling Algorithm of RC4中被提到。该攻击利用RC4中的密钥调度算法（KSA）的弱点来从加密消息中重构出密钥。FMS攻击在一些网络工具（例如AirSnort、weplab和aircrack）中得到了普及应用，这些工具使用该攻击来恢复受WEP保护的无线网络的密钥。

攻击描述

在WEP中，不仅仅有用户所输入的key，同时也有设置好的iv（initialization vector），WEP会将它俩拼在一起作为RC4的密钥调度算法中所输入的key，即inputKey = iv + key，这样可以防止key复用所导致的一些问题，但是这也并不是安全的。

现在我们来重点关注密钥调度算法。我们将经过了t次迭代的state记为St，这时的index分别记为it和jt。同时我们设所使用的IV的长度为I（假设I = 3），用户所输入的key为SK，inputKey的长度为L，则inputKey（记为K）表示为：

假设我们知道IV、加密过的密文和明文的第一个字节（在WEP中固定为aa），我们尝试从第一个我们不知道的key开始着手，设它在SK中的索引为A，则在K中的索引为A+3。当我们的IV都是诸如（A+3，N-1=255，V）的形式（其中V可以是任何值），我们可以有如下结论：

在经过了第一轮密钥调度算法中的迭代后，status如下所示：

其中上方的第一行是K，中间的数字是每个元素的索引值，最下方的一行是status。

在经过了第二轮密钥调度算法中的迭代后，status如下所示：

在取到K[A+3]，即攻击者不知道的第一个key的字节之前，status都是可以被攻击者所计算出来的（即S(A+3)之前的状态），如果在第二轮迭代后的S[0]和S[1]有受到更改，则攻击者可以丢弃使用该IV的情形

如果S[0]和S[1]没有受到更改，则在S(A+2)到S(A+3)的更新过程中，j会进行如下变化：

然后会进行self.__swap_state(i, j)，这个时候的status如下所示：

因为攻击者知道S(A+2)和j(A+2)，如果攻击者知道S(A+3)[A+3]的值，则攻击者可以知道它在S(A+2)中的位置（即j(A+3)的值），那么攻击者就可以计算出来K[A+3]的值。

为什么这样就可以计算出K[A+3]的值了呢？让我们关注伪随机子密码生成算法的部分，在对第一个明文字节进行加密的时候，密钥流（设为keyStreamByte）中的第一个字节的格式为：

则我们可以推出如下公式：

由于这里面除了K[A+3]我们都是知道的，那么我们就可以很容易地推出K[A+3]的值

上述公式中所使用到的states的值在S(A+2)到S(L-1)的更新过程中都没有受到更改的概率为：

在有足够的信息的时候，这个攻击是很容易实现并使用的

2020蓝帽杯决赛-infinite_game

这道题目的主要代码如下：

#!/usr/bin/env python3
import binascii
import os
import sys

FLAG = "flag{XXXXXX}"
KEY  = os.urandom(9)

def enhex(s):
    return binascii.hexlify(s.strip()).decode()

def unhex(s):
    return binascii.unhexlify(s.strip())

def echo(msg):
    sys.stdout.write(msg)
    sys.stdout.flush()

class PRNG:
    def __init__(self):
        self.state  = [i for i in range(256)]
        self.i      = 0
        self.j      = 0

    def __swap_state(self, a, b):
        self.state[a], self.state[b] = self.state[b], self.state[a]

    def ksa(self, key):
        j = 0
        for i in range(256):
            j = (j + self.state[i] + key[i % len(key)]) % 256
            self.__swap_state(i, j)

    def prng(self):
        self.i = (self.i + 1)                   % 256
        self.j = (self.j + self.state[self.i])  % 256
        self.__swap_state(self.i, self.j)

        return self.state[(self.state[self.i] + self.state[self.j]) % 256]

def do_typing():
    echo("iv > ")
    iv = unhex(input())
    if len(iv) != 3: 
        echo("ERROR: The length of IV must be 3.\n")
        return

    prng = PRNG()
    prng.ksa(iv + KEY)
    plaintext  = b"The Big Monkey is now typing...:" + os.urandom(128)
    ciphertext = b''
    for i in range(len(plaintext)):
        ciphertext += bytes([plaintext[i] ^ prng.prng()])
    
    echo("Tac, tac, tac... The monkey is typing: " + enhex(ciphertext) + "\n")

def do_pay_flag():
    echo("iv > ")
    iv = unhex(input())
    if len(iv) != 3: 
        echo("The length of IV must be 3.\n")
        return
    
    echo("input > ")
    ciphertext = unhex(input())

    prng = PRNG()
    prng.ksa(iv + KEY)
    plaintext = b''
    for i in range(len(ciphertext)):
        plaintext += bytes([ciphertext[i] ^ prng.prng()])

    if b"There is nothing either good or bad, but thinking makes it so." in plaintext:
        echo("The infinite monkey theorem is true. " + FLAG + "\n")

    echo("Done.\n")

def main():
        echo("""\

                      __,__
             .--.  .-"     "-.  .--.
            / .. \/  .-. .-.  \/ .. \\                  
           | |  '|  /   Y   \  |'  | |
           | \   \  \ 0 | 0 /  /   / |                  
            \ '- ,\.-"`` ``"-./, -' /                    T H E   I N F I N I T E   M O N K E Y   G A M E
             `'-' /_   ^ ^   _\ '-'`
             .--'|  \._ _ _./  |'--.                            
           /`    \   \.-.  /   /    `\\                             0> Start typing
          /       '._/  |-' _.'       \\
         /          ;  /--~'   |       \\                           1> Pay flag
        /        .'\|.-\--.     \       \\
       /   .'-. /.-.;\  |\|'~'-.|\       \\                         2> Exit
       \       `-./`|_\_/ `     `\\'.      \\
        '.      ;     ___)        '.`;    /         
          '-.,_ ;     ___)          \/   /
           \   ``'------'\       \   `  /
            '.    \       '.      |   ;/_
     jgs  ___>     '.       \_ _ _/   ,  '--.
        .'   '.   .-~~~~~-. /     |--'`~~-.  \\
       // / .---'/  .-~~-._/ / / /---..__.'  /
      ((_(_/    /  /      (_(_(_(---.__    .'
                | |     _              `~~`
                | |     \\'.
                 \ '....' |
                  '.,___.'

        \n""")
        
        while True:
            print("key:",KEY.hex())
            echo("\nInput your choice> ")
            choice = input()
            if not choice.strip():
                continue
            choice = int(choice)

            if choice == 0:
                do_typing()
            elif choice == 1:
                do_pay_flag()
            elif choice == 2:
                break
            else:
                echo("Unknown choice\n")
                continue 
try:
    main()
except KeyboardInterrupt:
    pass
except Exception as err:
    print("*** Exception:", err, "***")

该挑战首先会在每次连接的时候生成一个随机的key，然后提供了两个功能，do_typing和do_pay_flag

在do_typing中，我们可以提供任意的长度为3的iv，它会使用iv+key来进行RC4的密钥调度算法，并且使用RC4的伪随机子密码生成算法来加密一段前32个字节是已知的明文并返回加密后的密文

在do_pay_flag中，我们可以提供任意的长度为3的iv和一段密文，它也和选项do_typing一样使用相同的方法来进行RC4算法的使用，并解密我们所提供的密文，如果密文中有指定的明文段则会得到flag

这个场景就是我们上面所提到的FMS攻击的场景，那么按照上面的描述进行攻击即可：

#!/usr/bin/env python
from pwn import *
from tqdm import tqdm
from Crypto.Util.number import *
#context.log_level = "debug"

plain = b"There is nothing either good or bad, but thinking makes it so."
key_length = 9

# Helper function, which swaps two values in the box.
def swapValueByIndex(box, i, j):
    temp = box[i]
    box[i] = box[j]
    box[j] = temp

# Initialize S-box.
def initSBox(box):
    if len(box) == 0:
        for i in range(256):
            box.append(i)
    else:
        for i in range(256):
            box[i] = i

# Key schedule Algorithm (KSA) for key whose value is in unicode.
def ksa(key, box):
    j = 0
    for i in range(256):
        j = (j + box[i] + ord(key[i % len(key)])) % 256
        swapValueByIndex(box, i, j)

class PRNG:
    def __init__(self):
        self.state  = [i for i in range(256)]
        self.i      = 0
        self.j      = 0

    def __swap_state(self, a, b):
        self.state[a], self.state[b] = self.state[b], self.state[a]

    def ksa(self, key):
        j = 0
        for i in range(256):
            j = (j + self.state[i] + key[i % len(key)]) % 256
            self.__swap_state(i, j)

    def prng(self):
        self.i = (self.i + 1)                   % 256
        self.j = (self.j + self.state[self.i])  % 256
        self.__swap_state(self.i, self.j)

        return self.state[(self.state[self.i] + self.state[self.j]) % 256]

def cmd(idx):
    r.sendlineafter("Input your choice> ",str(idx))

def typing(iv):
    cmd(0)
    r.sendlineafter("iv > ",iv)
    r.recvuntil("Tac, tac, tac... The monkey is typing: ")
    result = int(r.recvuntil("\n",drop = True),16)
    result = long_to_bytes(result)
    return result

def getflag(iv,cipher):
    cmd(1)
    r.sendlineafter("iv > ",iv)
    r.sendlineafter("input > ",cipher)
    r.recvuntil("The infinite monkey theorem is true. ")
    flag = r.recvuntil("\n",drop = True, timeout = 2)
    return flag

r = process(argv=["python3", "chall.py"])
#r = remote("8.131.246.36",12180)
iv = [0,255,0]
rows = []
for A in tqdm(range(key_length)):
    iv[0] = A + 3
    for thirdByte in range(256):
        iv[2] = thirdByte
        cipherByte = typing(bytes(iv).hex())[0]
        rows.append([iv[0],iv[1],iv[2],cipherByte])

box = []
plainKnown = "54"
key = [None] * 3
for A in range(key_length):
    prob = [0] * 256
    for row in rows:
        key[0] = int(row[0])
        key[1] = int(row[1])
        key[2] = int(row[2])
        j = 0
        initSBox(box)
        for i in range(A + 3):
            j = (j + box[i] + key[i]) % 256
            swapValueByIndex(box, i, j)
            if i == 1:
                original0 = box[0]
                original1 = box[1]
        i = A + 3
        z = box[1]
        if z + box[z] == A + 3:
            if (original0 != box[0] or original1 != box[1]):
                continue
            keyStreamByte = int(row[3]) ^ int(plainKnown, 16)
            keyByte = (keyStreamByte - j - box[i]) % 256
            prob[keyByte] += 1
        higherPossibility = prob.index(max(prob))
    key.append(higherPossibility)

userInput = key[3:]
result = [format(key, 'x') for key in userInput]
rawkey = ''.join(result)
rawkey = rawkey.ljust(18,"0")
print(rawkey)
iv = "777777"
key = long_to_bytes(int(iv + rawkey,16))
prng = PRNG()
prng.ksa(key)
cipher = b''
for i in range(len(plain)):
    cipher += bytes([plain[i] ^ prng.prng()])
cipher = cipher.hex()
flag = getflag(iv,cipher)
print(flag)
r.close()

Reference

https://en.wikipedia.org/wiki/RC4

https://link.springer.com/content/pdf/10.1007%2F3-540-45537-X_1.pdf

https://github.com/jackieden26/FMS-Attack