第 21 卷 第 3 期 南 京 邮 电 学 院 学 报 ( 自 然 科 学 版) Vol. 21 No.3
2001 年 9 月 Journal of Nanjing University of Posts and Telecommunications ( Natural Science) Sep. 2001
文章编号: 1000- 1972( 2001) 03- 0028- 05
密码协议的形式化分析与设计原则
徐晓东, 岳殿武
( 南京邮电学院 通信工程系, 江苏 南京 210003)
摘 要: 介 绍了密码协 议的形式 化分析方法 和设计原则 , 着重 介绍了 BAN 逻 辑及其发展 以及一些 重要
的协议设计原则, 并提出了作者的一些观点。
关键词: BAN 逻辑; 密码协议分析; 密码协议设计; 鉴权; 认证协议
中图分类号:TN918. 1 文献标识码: A
1 简 介
密码协议是一类使用密码技术来达成特定任务
的协议, 协议参与者可以互不信任。例如, 大嘴青
蛙协议:
消息 1: A → S: A , { T
a
, B , K
ab
}
K
as
消息 2: S → B : { Ts , A, K ab } K
bs
其中, A、B 表示协议的参与者; S 表示认证服务器;
K 为密钥, 其下标表示共享该密钥的主体; { X } K 表
示用密钥K 加密X ; T a , T s 分别为A , S 的时戳; → 表
示消息的流向。大嘴青蛙协议或许是采用对称密钥
和认证服务器的最简协议, 其目的是从 A 经S 传送
给B 密钥K
ab
。
在分布式计算环境中, 经常采用密码协议以达
到识别用户, 建立共享密钥等目的。然而, 密码协议
的设计却存在很多问题, 许多广为人知的密码协议
刚提出不久就被发现存在严 重的错误, 例如 Need-
ham-Schroeder 协议
[ 1]
。
为此, 许多改进措施被提出。一种方法是形式
化的数学证明, 从系统化的协议验证工具例如 BAN
逻辑
[ 2]
到具体证明协议的安全等价于一些 NP 难解
问题例如大数因式分解。另一种方法是采用结构化
的设计原则, 即根据实践经验, 总结出谨慎的密码协
议设计原则来指导密码协议的设计, 如见文献[ 3] 和
[ 4] 。
这两种方法, 形式化的数学证明和结构化的设
收稿日期: 2001-04- 24
计原则, 在许多方面是互补的。一方面, 高效合理的
设计原则有助于构造更便于形式化逻辑验证的密码
协议; 另一方面, 由形式化分析所发现的错误可以改
进密码协议的设计原则。
2 BAN 逻辑及其发展
采用形式语言对密码协议进行安全性分析有 4
种基本途径:
(1) 采用非专门的说明语言和验证工具来建立
协议模型并加以验证;
( 2) 通过开发专家系统, 对密码协议进行开发
与研究;
( 3) 采用能够分析知识和信任的 逻辑, 对协议
进行安全性研究;
( 4) 基于密码系统的代数特点, 开发某种形式
方法, 对协议进行分析和验证。
途径( 3) 的应用最为广泛, 尤其是在实现密钥分
配的认证协议的分析中, 其代表是 BAN 逻辑。BAN
逻辑把参与认证的主体在协议运行后所持有的信仰
看作是认证协议的目标, 该逻辑从理想化的协议和
初始假设出发, 应用逻辑规则, 对协议运行中的逻辑
命题进行推理, 最终推出参与协议运行的主体所持
有的信仰。BAN 逻辑不考虑协议的具体实现不当导
致的错误和不可信主体的认证问题; 它关注的是协
议中可信主体持有的信仰, 以及由于协议的运行而
产生的信仰的演化。
BAN 逻辑的逻辑构造简述如下:
( 1) P sees X : 用 P X 表示, 即主体 P 收到包