6 个版本 (3 个重大更新)

0.4.1 2021年10月26日
0.4.0 2021年8月27日
0.3.1 2020年11月6日
0.3.0 2020年9月17日
0.1.0 2020年2月6日

#562开发工具

每月 22 次下载

MIT 许可证

290KB
4K SLoC

pitchfork: 使用符号执行验证常量时间代码

crates.io License

pitchfork 是一个工具,用于验证常量时间代码确实是常量时间的。它可以分析用 C/C++、Rust 或任何其他可以编译为 LLVM 位码(例如 Swift、Go 等)的语言编写的代码。给定一个要分析的函数,pitchfork 将会报告该函数是否是常量时间的,或者给出一个详细说明为什么它不是常量时间的解释,包括原始源代码中常量时间违规的行号、导致违规的完整分支决策序列,以及违规点所有变量的值。

pitchfork 是建立在 haybale 符号执行引擎之上的,该引擎也是用 Rust 编写的。

什么是常量时间,什么是常量时间违规?

常量时间编程是加固加密实现以抵抗时间侧信道攻击的事实上的技术;几乎所有主要的加密库都已采用。常量时间代码遵循两个基本原则

  1. 秘密值不得影响控制流(例如,分支条件或跳转目标),
  2. 秘密值不得影响内存访问的地址(例如,数组索引)。

这些原则确保程序的时间特性和内存访问模式与其操作的秘密值完全独立。因此,即使强大的时间侧信道攻击——特别是针对处理器缓存的 缓存攻击——也无法恢复关于这些秘密值的信息。

入门

1. 安装

pitchforkcrates.io 上,名称为 haybale-pitchfork。您可以在 Cargo.toml 中将其作为依赖项添加,选择与您想要的 LLVM 版本相对应的功能。

[dependencies]
haybale-pitchfork = { version = "0.4.1", features = ["llvm-12"] }

目前支持的 LLVM 版本有 llvm-9llvm-10llvm-11llvm-12

如果你想在代码中使用 pitchfork 而不是 haybale_pitchfork,可以使用 Cargo 的 依赖重命名 功能

[dependencies]
pitchfork = { package = "haybale-pitchfork", version = "0.4.1", features = ["llvm-12"] }

因为它是基于 haybale 构建的,pitchfork 也间接依赖于 LLVM 和 Boolector 库,这两个库都必须在你的系统上可用。有关更多详细信息和建议,请参阅 llvm-sysboolector-sys 的 README。

2. 获取要分析的位代码

由于 pitchfork 操作于 LLVM 位代码,你需要一些位代码才能开始。如果你想要分析的程序或函数是用 C 编写的,可以使用 clang*.bc 文件生成 LLVM 位代码,通过 -c-emit-llvm 标志

clang -c -emit-llvm source.c -o source.bc

为了调试目的,你可能还想要 LLVM 文本格式 (*.ll) 文件,你可以使用 clang-S-emit-llvm 标志生成

clang -S -emit-llvm source.c -o source.ll

如果你想要分析的程序或函数是用 Rust 编写的,你也可以使用 rustc--emit=llvm-bc--emit=llvm-ir 标志

注意,为了使 pitchfork 能够打印常量时间违规和其他错误的信息(例如,源文件名和行号),LLVM 位代码需要包含调试信息。你可以在生成位代码时通过向 clangclang++rustc 传递 -g 标志来确保包含调试信息。

3. 创建项目

Project 包含当前正在分析的代码,这些代码可能是一个或多个 LLVM 模块。要开始,只需从一个位代码文件创建一个 Project

let project = Project::from_bc_path(&Path::new("/path/to/file.bc"))?;

有关创建 Project 的更多方法,包括分析整个库,请参阅 Project 文档

4. 检查函数中的常量时间违规

假设我们想要检查以下 C 函数中的常量时间违规

int foo(int x) {
    if (x > 10) {
        return x % 200 * 3;
    } else {
        return x + 10;
    }
}

我们可以使用 check_for_ct_violation_in_inputs() 来分析此函数,将其所有输入(在这种情况下为 x)视为秘密

let result = check_for_ct_violation_in_inputs("foo", &project, Config::default(), &PitchforkConfig::default());

然后打印分析结果

println!("{}", result);

由于 x 影响分支条件,pitchfork 报告了常量时间违规。

用户指南:分析函数

在上面的“入门”示例中,我们使用了 check_for_ct_violation_in_inputs(),它将函数的所有输入视为秘密。然而,有时一些输入是公开的,而其他输入是秘密的。或者有时我们有一些指向秘密数据的指针作为参数,或者秘密数据隐藏在结构体内部。

更通用的函数 check_for_ct_violation() 接受两个额外的参数,有助于将数据标注为公共或秘密:argssd。在本节中,我们将分析更多函数的示例,展示更多标注公共和秘密数据的方法。

指定某些函数参数为公共

考虑以下C函数

int ct(int x, int y, int option) {
    volatile int z[3] = { 0, 2, 300 };
    z[2] = y;
    if (option > 3) {
        return z[1];
    } else {
        return z[2];
    }
}

如果我们使用 check_for_ct_violation_in_inputs() 分析此函数,我们将看到存在常量时间违规,因为 option 参数被用于分支条件

println!("{}", check_for_ct_violation_in_inputs("ct", &project, Config::default(), &PitchforkConfig::default()));

但是,假设此函数的 option 参数实际上只是表示某些配置选项,不应被视为秘密。我们可以通过使用更通用函数 check_for_ct_violation()args 参数来将此信息传达给 pitchfork

args 迭代器的每个元素描述了 ct() 的相应参数。 args 的元素类型为 AbstractData;有各种不同的方式来描述参数,但让我们关注最基本的两点

  • AbstractData::default() 是最重要的选项。它使用 StructDescriptions 中的信息和 LLVM 位码中的类型信息来自动生成参数的适当描述。我们将在稍后详细讨论 StructDescriptions;现在,重要的是除非 StructDescriptions 有不同说明,否则标记为 default() 的任何内容都将被视为 公共
  • AbstractData::secret() 是标记参数为秘密的最简单方法。它使用 LLVM 位码中的类型信息根据参数的大小自动生成适当的描述,这次将其标记为秘密。请注意,如果参数是指针,这可能不会按预期工作;请参阅下文关于指针参数的部分。

对于上面的 ct() 函数,我们可以使用以下参数描述来分析它

println!("{}", check_for_ct_violation(
    "ct",
    &project,
    Some(vec![AbstractData::secret(), AbstractData::secret(), AbstractData::default()]),
    &StructDescriptions::new(),
    Config::default(),
    &PitchforkConfig::default(),
));

这次,pitchfork 应该报告该函数是常量时间的。

指定某些函数参数的特定值

让我们考虑上面提到的 ct() 函数的一个略微不同的变体

int ct(int x, int y, int option) {
    volatile int z[3] = { 0, 2, 300 };
    z[2] = y;
    if (option > 3) {
        return z[1];
    } else {
        return z[x % 3];
    }
}

如果我们使用上面给出的注释来分析这个函数,pitchfork会(正确地)报告一个常数时间违规,因为z[x % 3]使用了一个依赖于秘密数据的数组索引。

但是,让我们假设我们只对分析option值为5的情况感兴趣。我们可以用AbstractData来这样表达

println!("{}", check_for_ct_violation(
    "ct",
    &project,
    Some(vec![
        AbstractData::secret(),
        AbstractData::secret(),
        AbstractData::pub_i32(AbstractValue::ExactValue(5)),
    ]),
    &StructDescriptions::new(),
    Config::default(),
    &PitchforkConfig::default(),
));

这里我们使用AbstractData::pub_i32()来指定一个公共32位整数,并使用AbstractValue::ExactValue(5)来赋予这个整数确切的值5。这意味着分析只会考虑该参数值为5的情况,结果会报告该函数没有常数时间违规。

ExactValue在函数参数指定像输入数组长度这样的东西时也很有用,而你只想在分析中考虑特定的数组长度。有关指定参数值的其他方法,请参阅AbstractValue的文档。

作为一个旁注,请注意,您不能指定标记为秘密的东西的值。这是因为标记为秘密的任何东西的值对于符号分析来说并不重要。事实上,如果标记为秘密的某物的值对于分析很重要(例如,确定哪些路径是有效的,或者哪个内存地址被加载),那么这已经是一个常数时间违规,因为这意味着秘密值已经影响了分支条件或内存地址。

指向秘密数据数组的指针

假设我们有一个C函数,它接受一个指向32个秘密整数的数组的指针,并将1加到数组的每个元素上

uint32_t secret_array(uint32_t* arr) {
    for (int i = 0; i < 32; i++) {
        arr[i] += 1;
    }
    return arr[0];
}

arr使用AbstractData::secret()可能不会按预期工作

println!("{}", check_for_ct_violation(
    "secret_array",
    &project,
    Some(vec![AbstractData::secret()]),
    &StructDescriptions::new(),
    Config::default(),
    &PitchforkConfig::default(),
));

这个函数看起来没有问题,但pitchfork会报告一个常数时间违规!这是因为它将secret应用于参数本身,在这个例子中是一个指针。由于指针值arr是秘密的,因此访问arr[i]的结果是一个依赖于指针arr的秘密值的地址。

相反,我们可以告诉pitchforkarr本身(指针)是公开的,但它指向一个秘密数据的数组

AbstractData::pub_pointer_to(AbstractData::array_of(AbstractData::secret(), 32))

我们还需要提高“循环界限”,默认值为10(截至本文撰写时)。(有关更多详细信息,请参阅有关Config.loop_bound的文档。)

let mut config = Config::default();
config.loop_bound = 100;
// then pass this `config` to `check_for_ct_violation()`

现在,pitchfork应该验证函数是否是常数时间的。

有关数组的更多约束

以下C函数接收两个数组的指针:包含公共值的数组 public_arr,其长度为 public_arr_len,以及包含秘密值的数组 secret_arr,长度为32。假设 public_arr_leni 也是公开的 - 唯一的秘密值在 secret_arr 中。

uint32_t secret_array_var_length(uint32_t* public_arr, uint32_t public_arr_len, uint32_t* secret_arr, uint32_t i) {
    uint32_t x = public_arr[i];
    for (int j = 0; j < 32; j++) {
        secret_arr[j] += x;
    }
    if (x > 10) {
        return public_arr[0] + secret_arr[0];
    } else {
        return public_arr[1] + secret_arr[1];
    }
}

如果我们像这样检查该函数的常量时间违规行为...

println!("{}", check_for_ct_violation(
    "secret_array_var_length",
    &project,
    Some(vec![
        AbstractData::default(),
        AbstractData::default(),
        AbstractData::pub_pointer_to(AbstractData::array_of(AbstractData::secret(), 32)),
        AbstractData::default(),
    ]),
    &StructDescriptions::new(),
    config,  // with loop_bound set to 100 as above
    &PitchforkConfig::default(),
));

...我们会发现 pitchfork 报告了一个常量时间违规。具体来说,如果 i 太大,public_arr[i] 实际上会从 secret_arr(在 public_arr 的末尾)加载秘密数据,然后用于分支条件。

在这种情况下,只要调用者传递一个在范围内 i,函数实际上是安全的。为了仅分析 i 在范围内的情况,我们可以为 public_arr 指定一个最大长度(在这个例子中,让我们假设72个元素),并将 public_arr_leni 都约束在这个最大长度内

println!("{}", check_for_ct_violation(
    "secret_array_var_length",
    &project,
    Some(vec![
        AbstractData::pub_pointer_to(AbstractData::array_of(AbstractData::default(), 72)),
        AbstractData::pub_i32(AbstractValue::Range(0, 72)),
        AbstractData::pub_pointer_to(AbstractData::array_of(AbstractData::secret(), 32)),
        AbstractData::pub_i32(AbstractValue::Range(0, 71)),
    ]),
    &StructDescriptions::new(),
    config,  // with loop_bound set to 100 as above
    &PitchforkConfig::default(),
));

有了这些注释,pitchfork 将验证在给定这些假设的情况下函数是常量的。

注意关于此函数的两个额外事项:首先,我们可以在不知道其实际长度的情况下选择一个较大的 public_arr 最大长度。假设数组的大小并不会真的造成伤害:pitchfork 将为该数组“分配”额外的内存,但该内存将不会被使用,并且(很可能)不会影响分析。其次,上述分析仍将考虑 i > public_arr_len 的输入;只是上面的函数在这些情况下仍然是常量的,因为我们假设 ipublic_arr 实际分配的大小内(72,尽管 public_arr_len 可能更小)。如果我们想考虑那些同时满足 i < public_arr_len 的案例,我们可以用这个用于 public_arr_len

AbstractData::pub_i32(AbstractValue::named("public_arr_len", AbstractValue::Range(0, 72)))

和这个用于 i

AbstractData::pub_i32(AbstractValue::UnsignedLessThan("public_arr_len".into()))

您可能会想知道当我们使用 AbstractData::default() 时,pitchfork 首先对 public_arr 做了什么假设。答案是它假设了一个长度为 AbstractData::DEFAULT_ARRAY_LENGTH 的数组(截至本文写作时为1024)。有关 default() 的精确行为的更多详细信息,请参阅有关 AbstractData::default() 的文档。

包含秘密数据的结构体

让我们考虑这个C函数

uint32_t uses_a_struct(Context* ctx, uint32_t* public_input, uint32_t* public_output) {
    for (int i = 0; i < 32; i++) {
        public_output[i] = public_input[i] ^ ctx->secret_key;
    }
    if (ctx->public_option) {
        return public_output[0];
    } else {
        return public_output[1];
    }
}

其中,Context 结构体定义为

typedef struct {
    uint32_t public_option;
    uint32_t another_thing;
    uint32_t secret_key;
} Context;

我们希望指定 ctx 参数指向一个包含一些秘密数据(secret_key)和一些公共数据(public_option)的结构体。我们可以使用 AbstractData::_struct 来实现这一点

println!("{}", check_for_ct_violation(
    "uses_a_struct",
    &project,
    Some(vec![
        AbstractData::pub_pointer_to(AbstractData::_struct("Context", vec![
            AbstractData::default(),  // public_option
            AbstractData::default(),  // another_thing
            AbstractData::secret(),   // secret_key
        ])),
        AbstractData::default(),  // public_input
        AbstractData::default(),  // public_output
    ]),
    &StructDescriptions::new(),
    config,  // with loop_bound set to 100 as above
    &PitchforkConfig::default(),
));

有了这个描述,pitchfork 应该能够正确报告该函数是常量的。

另一种实现相同功能的方法——如果存在多个Context结构体或者有其他结构体包含指向Context结构体的指针等,这种方法将更有用——是通过StructDescriptions。我们可以向pitchfork提供一个Context结构体的描述。

let sd: StructDescriptions = vec![
    ("struct.Context".into(), AbstractData::_struct("Context", vec![
        AbstractData::default(),  // public_option
        AbstractData::default(),  // another_thing
        AbstractData::secret(),   // secret_key
    ])),
].into_iter().collect();

然后,当我们使用AbstractData::default()时,它将自动考虑我们在StructDescriptions参数中给出的Context结构体的描述。

println!("{}", check_for_ct_violation(
    "uses_a_struct",
    &project,
    Some(vec![
        AbstractData::default(),  // ctx
        AbstractData::default(),  // public_input
        AbstractData::default(),  // public_output
    ]),
    &sd,
    config,  // with loop_bound set to 100 as above
    &PitchforkConfig::default(),
));

此外,它遇到的任何其他作为相同或不同参数的Context结构体也将使用这个描述。

使用Pitchfork的main_func

Pitchfork还提供了一个带有众多命令行选项的main_func(),用于对您选择的库进行恒时检查。您只需提供您的ProjectStructDescriptionsConfig等,然后在您的main()中调用main_func()即可。

依赖项

~10–20MB
~307K SLoC