)’ 可能存在一些不易发现的安全缺陷 # 有些甚至数年后 才被 发现 & 长期 以 来 # 形式化方法被公认为分析安全 +
协议的有力武器 + 目前分 析 安 全 协 议 的 形 式 化 方 法 主 要 有 $ 该 方 法 基 于 知 识 和 信 念 推 理 的 模 态 逻 辑# 如 ! 推 理 构 造 法#
! " " &年&月 第’ ’卷!第’期
!
西安电子科技大学学报 （自然科学版） ! "#$%& ’!" (!) * + * &%!#% * , -$ . * /0
!
U < A+ ! " " & V 8 + ’ ’!P + ’
一种形式化分析安全协议的新模型
慕建君
! 西安电子科技大学 计算机学院 " 陕西 西安 !% # ) " " % ) 摘要 ! 串空间是安全协议形式化分析的一种新模型 + 利用次序关系的理论证明了借助串空间模型进行 安全协议形式化分析的一个重要结论 + 通过构造 入 侵 者 串 的 方 法 ! 针对 , $ . / 0 协议提出了一个入侵 者串空间模型 ! 同时利用此入侵者串空间模型分 析 了 该 协 议 存 在 的 缺 陷 ! 说明了改进后的 , $ . / 0协 议可克服此缺陷 + 与现有安全协议形式化分析方法 相 比 较 ! 串空间模型不仅具有简洁直观的优点! 而且 还可避免状态空间爆炸的问题 + 关键词 ! 安全协议 " 形式化分析 " 串空间模型 " 入侵者串 中图分类号 ! " # 1 2 ’ " *!! 文献标识码 ! 3!! 文章编号 ! ) " " ) $ ! ( " " ! " " & " ’ $ " ’ 4 ) $ " #
+ 串8 中& & ) 是& ! 的直接前驱 . )* & ! 表示在同一串上 & ) 是& ! 的前驱但不一定是直接前驱 + 0= &) . % 一个无符号项- 出现在结点& $ : 当且仅当- # > ? 0(
源于 ) 结点& $ : 如果0= 的符号为正且-# ! 但对于同一串上 &) 0= &) & 一个无符号项-产生于 ( > ? 0( > ? 0( , 结点 & 的任何前驱& <有 -# 0= & <) . > ? 0( ’ 一个无符号项- 惟一产生的如果- 产生于惟一的结点& $ : . 容易看出 ! 结点集 : 与边& ! ( & ) ’& ! 和& )* ! 的集合一起构成了一个有向图 " & ’+ * )# . ! " $! 束和次序关系 一 个束表示在某一具体情形下一个协议的执行过程 ! 它是有向图 "&! ( 此子图 ’+ * ) # 的有限子图 ! 中的边表示结点之间的因果依赖关系 + 定义 %! 假设 ’= ,’ ! 令 > 2 " :> ! ( ( 其中 :> 表 *= , * . ’= + *=) # 是 " :! ’+ * ) # 的子图 !
&’ ’’ 但K 而不能分析协议的保密性质 & % 该方 K 3P 逻辑 ! 等 # 3P 逻辑只能分析协议的认证性质 # " 攻击构造法 # 法从协议的初始状态开始 # 对合法主体和一个攻击者所有可能的执行路径进行穷尽搜索 # 以期找到协议可能 &’ & #’ 存在的错误 + 这种方法主要有基于模型检测技术的模型检测器 Q 验证语言 M 代数 简化 理论模 R S( ( < ? ! ( & &# %’ 型以及特定专家系统 ! 如特殊目的 PS " # 但这种方法无法解决状态空间爆炸问 . 分 析 器 和T A = > ? ? / = ? C
$ ! 5 0 3 * + 1 3 = ? / A BI / 6 > @ I /A > J0 B > 8 9 ? = 7 > 9 ? 0 / 8 / A / 8 I @ I9 I > 6 < ? @ = ? = 6 8 I + K !5 ; D D; D < I @ A 7 > = 7 > ? 9? B > ? ? > 8 / = @ A# /G > ? 0 ? = / A =6 A 6 8 < I @ A< I > B= -/ A / 8 L >I > 6 < ? @ = C= DD@ ; D D ? = 6 8 I 9 ? 0 / 8 8 @ = 7= 7 >7 > 8 9= 7 >I = ? / A BI / 6 >0 B > 8 @ II 7 J A+K A I = ? < 6 = @ A ; DJ ;; D6 C > A > = ? / = ?I = ? / A B I 9 ? = 7 >, $ . / 0; ? = 6 8J >; ? > I > A = /I = ? / A BI / 6 >0 B > 8 @ A 9 @ 8 = ? / = > B ; ; #J 9 ? = 7 @ I; ? = 6 8 +M ? > G > ? @ = 7= 7 >7 > 8 9= 7 @ II = ? / A BI / 6 > 0 B > 8@ A 9 @ 8 = ? / = > B J > ; ; / A / 8 L > = 7 >9 8 / J@ A= 7 @ I; ? = 6 8/ A B@ 8 8 < I = ? / = >= 7 / == 7 @ I9 8 / J@ A= 7 @ I; ? = 6 86 / AN > D G > ? 6 0 > @ A= 7 > @ 0 ? G > B, $ . / 0; ? = 6 8 +1 7 >I = ? / A BI / 6 >0 B > 8B @ I 6 < I I > B/ N G > ; ; @ IB @ I = @ A < @ I 7 > B9 ? 0= 7 > ?0 B > 8 IN = II @ 0 8 @ 6 @ = A B6 / A/ G @ B= 7 >I = / = >I / 6 > C D@ ; D/ ; > O 8 I @ A; ? N 8 > 0+ ; $ % % % 6 # & * ’ 0 > 6 < ? @ = ? = 6 8 9 ? 0 / 8 / A / 8 I @ I I = ? / A BI / 6 >0 B > 8 > A > = ? / = ?I = ? / A B !I D; D ; ; ,7 安全协议是采用密码技术来保障通信各方之间安全交 换信息 的一个 规则 序 列 # 其目的是在通信各方之 间提供认证或为新的会话分配会话密钥 + 尽管现有的安全协议是安全专家精心设计和详细审核过的 # 但仍然
收稿日期 ! ! " " # $ " # $ ! % 基金项目 ! 国家自然科学基金资助项目 ! " & " # % ’ " ’ ( 作者简介 ! 慕建君 ! " # 男# 副教授 # 博士 + ) * & # $
自然科学版 " ’卷 !!!!!!!!!!! !!!!! 西安电子科技大学学报 ! !!!!!!!!!!! !!!!! 第 ’ ’ 4 !
8! 串空间模型
! " !! 项和子项 * 中的元素称为项 + !! 设 * 表示一个协议中参与者之间可能交换的所有消息的集合 ! 定义 !! 符号项是一个有序对 ""! 其中 % $ *! ! 记一个符号项为 +-或 ,! % #! +! ,& +-表示 "$ % % 发出项’ ( ,- 表示接收到项-. /*) 表示符号项的有限序列的集合 + 设 0 表示原子信息集合 ! 且 0 & 1 23! 通常假设集合 * 是由集合 1 和0 在求逆密钥 1 表示密钥集合 ! 加密 % 4 * 5& 5! 下生成的自由信息空间代数 + 4 和级联运算 5) 定义 #! 设 * 自由信息空间代数 ! 可递归定义为 + 有% # * 上的子项关系 # %’ ! 对所有的% 2- $0!
) ,
有% # ! 则% # % 或 %’ 4 $1) " 对所有 的% 2 4 $1 ! # 若% # $ 若% # 6 或% 2 % 6& 6 $*! 6& 6! 4 ( 4’ ! 则% # 7( 7. %# 7 或% 26 7 $*) 6 $*! 6 ! " #! 串和串空间 串是一个参与者可能参与的事件序列 + 对于合法参与 者 ! 每个 串是接收 和 发 送 的 消 息 序 列 ! 表示该参与 者在一次特定协议执行中的行为以及所有数据项 ( 如 密 钥和临 时值 ) 的特 定值 + 攻击 者 串 是 攻 击 者 可 能 发 送 和接收的消息序列 + 定义 $! 设 * 为自由信息空间代数 ! * 上的一个串空间是包含各种合法主体串和攻击者串的集合# 及
Байду номын сангаас