0x01 口胡

流密码由于其适合在硬件上的高效实现，所以在发明初期也是应用广泛，其中流密码在现实中最广为人知的应用要数A5算法了。A5在1989年由法国人开发，用于GSM系统的序列密码算法，它用于对从电话到基站连接的加密，先后开发了三个版本记作A5/1、A5/2、A5/3，如果没有特别说明，通常所说的A5是指A5/1，关于GSM加密问题，一些人认为会因为密码的问题阻碍手机的推广，另一些人则认为A5太弱，不能抵抗一些情报机构的窃听，A5的特点是效率高，适合硬件上高效实现，它能通过已知的统计检验，起初该算法的实际没有公开，但最终不慎泄漏。

0x02 正片

A5算法总的流程图：

A5/1算法使用3个线性反馈移位寄存器，简称为LFSR，我们分别将其标识为X、Y和Z。寄存器X有19位，可以表示为(x0, x1, … ,x18)；寄存器Y有22位，可以表示为(y0, y1, … ,y21)；而寄存器Z有23位，可以表示为(z0, z1,… ,z22)。这里要使用三个共包含64位二进制的线性反馈移位寄存器，这个设计绝非偶然。绝非巧合的是，A5/1算法的密钥K也是64位。该密钥用于三个线性反馈移位寄存器的初始填充，也就是说，该密钥用于充当三个寄存器的初始值。这三个寄存器用密钥填充之后，就可以开始生成密钥流了。

那么，它是如何生成密钥流的呢，现在我们给定初始密钥后，三个LFSR中已经有了初始状态，这三个LFSR是通过何种方式生孩子的呢？像上篇中我们讲的那样，对于每一个寄存器，它会通过向最高位的移动(产下处于最高位的孩子)来产生密钥，3个寄存器都通过这种操作来产生密钥，然后3个最高位经过异或操作得到最终的密钥。此时需要考虑的一个问题就是当最高位产下后，最低位的补充问题。对于最低位的补充，不同的寄存器采取不同的策略：对于X，即19位的LFSR，采取的策略是取当前状态的(从第0位开始算)第18、17、16、13位的异或值作为当前状态转换为下一状态时，下一状态的最低位的补充，代码体现为：

相似的，Y取21、20、16、12位，代码体现为：

Z取22、21、18、17，代码体现为：

这里之所以要po上代码图，是为了让大家感受如何通过位操作来实现我们的策略，体会位操作的精准与强大。

是不是每一次都会像上面所说的，每次3个LFSR移位，然后结果异或作为最终输出结果，而对于最低位的补充，不同的LFSR采取不同的策略。其实不然，并不是每一次3个寄存器都移动产生密钥流的，什么意思呢？就是说在一次密钥的产生过程中，并不是每个LFSR都会移动，但是对于最终密钥的产生，仍然会取三个LFSR中的最高位的异或值作为输出，只不过对于不移动的LFSR而言，它前后两次提供的密钥是相同的，应为它没有移动。而对于移不移动的问题，A5中采用的是一种叫做钟控的方式。描述为：给定三个二进制位x、y和z，定义多数投票函数maj(x, y, z)。也就是说，如果x、y和z的多数为0，那么函数返回0；否则，函数返回1。因为二进制位的个数为奇数，所以不会存在无法判决的情况，因此该函数的定义不会存在问题 。

在A5/1加密算法中，对于生成的每一个密钥流的位，都将执行如下操作。首先，我们计算：m=maj(x8, y10, z10)然后，执行寄存器X、Y和Z的各自步骤(或者不执行，根据计算执行结果的情况而定)如下：如果x8=m，那么执行X步骤(这里的X步骤即指我们上面所说的移动，然后最低位补充的意思，Y步骤和Z步骤也是这个意思)。如果y10=m，那么执行Y步骤。如果z10=m，那么执行Z步骤。最终，单独密钥流的位s通过如下计算生成：S=x18+y21+z22。即：

到这里，对于A5算法中3个LFSR的工作，即如何移动，是否移动，我们已经清楚了，也就是说，如果给定三个这样的LFSR，我们只需要给定一个64位的初始状态(初始密钥)，那么这3个LFSR就可以按照我们所想的那样去不停的产生密钥流了。

这只是A5算法理论上产生密钥流的过程，在具体的应用过程中，它还有很多不同之处。

A5算法的具体实战流程

1. 利用会话密钥k设定三个移存器的起点，即初始状态。
2. (帧序号参与) 三个LFSR都规则动作22次，每次动作1步。在第i步动作时，三个LFSR的反馈内容都首先与帧序号的第i比特模2加，并将模2加的结果作为LFSR反馈的内容；帧序号比特的序号是从最低位编到最高位。
3. 三个LFSR以钟控方式连续动作100次，但不输出乱数
4. 三个LFSR以钟控方式连续动作114次，在每次动作后，三个LFSR都将最高级寄存器中的值输出，这三个比特的模2和就是当前时刻输出的1比特乱数。
5. 连续动作114步，共输出114比特乱数，用于对用户手机到基站传送的114比特数据的加密。

对于上面的补充：

帧序号参与方式：与密钥参与方式相同，不同的明文数据帧按顺序编号，每个编号为22比特。帧密钥参与的目的：对不同的帧设置不同的帧会话密钥，保证对每帧以不同的起点生成乱数，尽可能避免密钥重用。

A5算法用于GSM系统中，也就是说，传输的数据以帧为单位，每帧的大小是114bit，科普下为什么是114bit：

gsm系统中，是将每20ms的模拟话音进行一次处理，将20ms的话音通过信源编码（rpe-ltp）处理成260bit的数字信号；再经过信道编码变换为456bit的数字信号，然后经过交织分成8个部分，每部分57bit；空中的时隙中，每个时隙承载2部分即114个bit的内容，于是20ms的话音完全通过4个时隙的资源承载。

知道了A5算法具体的加密流程，我们来看下A5在现实中具体的应用模型：

A5-1算法用于用户的手机到基站之间的通信加密，通信内容到基站后先脱密变成明文，然后再进行基站到基站之间、以及基站到用户手机之间的信息加密，完成通信内容在通信过程的加密保护。

这里，我们只需考察用户A到基站1之间通信内容的加脱密，中间消息的传送由基站到基站之间的加密完成，而接收方用户B对消息的加脱密与用户A到基站1之间的通信完全类似，只不过是用户B先脱密消息。

对于密钥：

基本密钥KA1：预置在SIM卡中，与基站1共享。
生存期：一旦植入SIM卡将不再改变。
用途：用来分配用户和基站之间的会话密钥。
注意：这里的基本密钥并非用来加密数据，而是用来加密在每一次的会话过程中的密钥，会话过程中数据的加密采用A5，而对于A5加密算法中的初始密钥，在用户和基站之间，一般是通过非对称密码体制产生的基本密钥(或密钥对)KA1来实现对每次通信过程所需的密钥进行加密，将密钥加密后进行传输，来达到让用户和基站之间在一次通信过程中共享同一个密钥的目的。

这里，我们对每次会话的密钥k做补充说明：

对于通信过程中数据(明文)的处理：

由于发送和接收是同时发生的，所以每帧的数据可以看成两个114bit，即228bit，这两个114bit所使用的密钥流是相同的。一次通话使用一个会话密钥，对每帧使用不同的帧密钥。所以一次通话量：至多222帧数据，约0.89×230比特 。

这里总结下具体的通信流程(以手机通信为例，只说明A与基站的通信):

1. 用户A与基站建立联系；
2. 基站得知用户A的身份，并知道用户A要与它通信，此时基站就会找到与用户A共享的密钥KA1(存在基站的数据库中)，当然这个密钥也会在用户A的SIM中存储着一份，然后基站随机产生64bit的密钥，作为此次通信中A5算法的初始密钥，对该密钥用KA1加密后，传递给用户A；
3. 用户A用存储在SIM中的与KA1相对应的密钥KA1对加密的密钥进行解密，得到此次通信过程中所需的密钥；
4. 用户A用得到的此次通信过程中的密钥对通信数据进行加密后传递给基站，加密的算法使用A5算法，由于SIM中内置A5算法的硬件实现，所以可以轻易实现该加密过程；
5. 基站在接收到用户A发送过来的数据后，由于基站中也有相应的A5算法的实现过程，且A和基站的A5算法的初始密钥相同，所以说，此时基站会产生与A相同的密钥流，然后对数据进行依顺序解密，从而得到用户A发送过来的明文数据；
6. 基站对用户A的响应过程类似；
7. 这样，用户A和基站之间就可以正常通信了

对于A5在通信过程中的应用模型大致就是这样，下面我们来看一下，如何对此种模型下数据的机密性造成破坏。

0x03 破坏即艺术

这里首先说明下，虽然A5属于流密码体系，但对于A5的破解，跟我们上一篇blog中提到的对流密码的破解是两个完全不同的概念，上篇blog中谈到的破解指得到了一串明密文对，我们想知道它是怎么加密的，根据破解的加密方式，我们可以由当前的密文得到接下来的密钥流，这样的话，我们在继续截获密文的情况下就可以根据前面破解的加密方式来得到的密钥流来对密文进行解密，从而得到相应的明文；但A5算法是完全不同的，A5是知道了加密方式的，它是对外公开的，而A5破解的关键是得到初始密钥，所以二者意义完全不同，破解的思路也就大不一样。

首先是针对A5算法本身，A5算法的加密强度弱，由于A5使用的加密密钥长度是64 bit的算法，现在超级计算机已经能在较短的时间内破解这些算法，所以对于A5算法的爆破我们不讨论，我们这里以一种类似于极客的眼光去看下如何对A5算法应用的这种通信模型造成破坏。

SIM卡的复制

在看完我写的该通信模型的流程之后，大家已经可以隐约意识到了这个通信模型的脆弱性，发挥你的想象力，去思考如何从其中的一环去破坏。对于该通信模型的破坏，首先就是SIM卡的复制了。

对于SIM卡，SIM卡存储有持卡者的用户数据、保密数据和鉴权加密算法等；
SIM卡和设备间有一个开放的公共接口，移动设备通过该接口读取SIM卡中的用户数据，并将数据发送给GSM网络，请求接入网络。由于这张卡上存储着你的用户信息，也就是说基站只认识你这张卡，所以说只要你能复制这张卡，你就是用户A的一个copy，那么数据的机密性也就无从谈起了。对于SIM卡的复制，已经有前人做过实验：

伪基站

既然用户A可以copy，那么基站自然也不是问题，伪基站模拟成一个真实的基站，与手机交互，实施鉴权过程，并且获得了手机用户的IMSI，对于其具体的原理，由于我也不是很懂，而且也没有找到相关资料，所以就不误导了。。。

---

A5/1加密算法是一个非常富有代表性的例子，该方案代表了一大类基于移位寄存器并以硬件实现的流加密算法。此类系统曾经在对称密钥加密领域大行其道，但是近年来，分组密码加密已经明显地占了上风，取代了流密码加密的昔日辉煌地位。