HKDF：算法规范、C++11实现与可证明安全分析

本文档完整阐述 RFC 5869 定义的 HMAC-based Extract-and-Expand Key Derivation Function (HKDF)，包含精确的算法定义、遵循 C++11 标准的 OpenSSL 实现，以及基于密码学规约的安全性分析。

1. 概述

HKDF 是一种基于 HMAC 的密钥派生函数，采用 “提取-扩展”（extract-then-expand）范式。其设计目标是将输入密钥材料（IKM）转换为一个或多个密码学意义上的强密钥，即使原始 IKM 并非均匀分布。

HKDF 的逻辑结构分为两个模块：

提取（Extract）：将可能质量参差的 IKM 浓缩为一个固定长度的伪随机密钥 PRK
扩展（Expand）：将 PRK 扩展为所需长度的一个或多个输出密钥

HKDF 的标准化文档为 RFC 5869（2010年5月发布），作者为 Hugo Krawczyk 和 Pasi Eronen。

2. 符号约定

符号	含义
`Hash`	底层哈希函数（如 SHA-256、SHA-512）
`HashLen`	哈希函数输出长度（字节）
`HMAC-Hash(K, M)`	以 K 为密钥、M 为消息的 HMAC 计算
`\|`	字节串拼接
`0x01`	单字节常量，值为1

其中，HMAC 定义为：

HMAC-Hash(K, M) = Hash((K' ⊕ opad) || Hash((K' ⊕ ipad) || M))

若 |K| > blockSize，则 K' = Hash(K)；否则 K' 为 K 左补零至 blockSize 字节
opad = 0x5C 重复 blockSize 次，ipad = 0x36 重复 blockSize 次

在 Extract 步骤中，IKM 作为 HMAC 的输入（消息），而非 HMAC 的密钥。

3. 算法规范

3.1 HKDF-Extract

输入：

salt：盐值（可选，非秘密随机值）。若未提供，置为 HashLen 个 0x00 字节
IKM：输入密钥材料

输出：

PRK：长度为 HashLen 字节的伪随机密钥

定义：

PRK = HMAC-Hash(salt, IKM)

约束：salt 为空时，明确设置为 HashLen 个零字节，而非 blockSize 个。

3.2 HKDF-Expand

输入：

PRK：伪随机密钥（长度至少为 HashLen，通常为 Extract 的输出）
info：上下文与应用特定信息（可选，可为零长度）
L：输出密钥材料长度（字节），满足 L ≤ 255 × HashLen

输出：

OKM：长度为 L 字节的输出密钥材料

定义：

N = ceil(L / HashLen)

T(0) = 空串
T(1) = HMAC-Hash(PRK, T(0) || info || 0x01)
T(2) = HMAC-Hash(PRK, T(1) || info || 0x02)
...
T(N) = HMAC-Hash(PRK, T(N-1) || info || 0x0N)

OKM = T(1) || T(2) || ... || T(N)
OKM = OKM 的前 L 字节

约束：计数器为单字节编码，范围 0x01 至 0xFF，因此最多 255 次迭代。若 L > 255 × HashLen，算法报错。

重要性质：HKDF 是可扩展输出函数（XOF）。在 IKM、salt、info 固定的情况下，长度为 L1 的输出是长度为 L2 ≥ L1 的输出的前缀。

3.3 HKDF 组合函数

HKDF(salt, IKM, info, L) =
    HKDF-Expand(HKDF-Extract(salt, IKM), info, L)

4. 参数使用规范

4.1 salt（盐值）

推荐使用：salt 显著增强 HKDF 强度，确保不同应用之间的独立性，支持”源无关提取”
性质：salt 是非秘密的，可重用
理想长度：等于 HashLen 的随机或伪随机字符串
不提供时：自动补零，但安全性低于提供随机 salt

4.2 info（上下文信息）

目的：将派生密钥绑定到应用与上下文特定信息，防止同一 IKM 在不同上下文中派生出相同的密钥材料
内容示例：协议号、算法标识符、用户身份、密钥长度 L
技术要求：info 应独立于 IKM 值

4.3 跳过 Extract 的适用场景

只有当 IKM 本身就是高质量伪随机密钥（均匀分布，长度等于 HashLen）时，可考虑跳过 Extract 直接使用 Expand。Diffie-Hellman 共享值等非均匀秘密必须执行 Extract。

5. C++11 完整实现

以下实现使用 OpenSSL 1.1.0+ EVP API，遵循 C++11 标准，并包含 RFC 5869 测试向量的验证。

5.1 头文件 (`hkdf.hpp`)

#ifndef HKDF_HPP
#define HKDF_HPP

#include <vector>
#include <cstdint>
#include <stdexcept>
#include <string>

#include <openssl/evp.h>
#include <openssl/hmac.h>

/**
 * HKDF - RFC 5869 完整实现
 * 基于 HMAC 的提取-扩展密钥派生函数
 * 
 * 线程安全：该类为无状态静态类，线程安全
 */
class HKDF {
public:
    enum class HashAlgo {
        SHA256,   // HashLen = 32, blockSize = 64
        SHA512    // HashLen = 64, blockSize = 128
    };

    /**
     * 组合函数：一步完成 Extract + Expand
     * 
     * @param salt      盐值（推荐为随机，长度 = HashLen）。空时自动补 HashLen 个 0x00
     * @param ikm       输入密钥材料
     * @param info      上下文信息（推荐填写以分离密钥）
     * @param length    输出长度（字节），必须 ≤ 255 × HashLen
     * @param algo      底层哈希算法
     * @return          OKM，长度为 length 字节
     * @throws std::invalid_argument  参数非法（length 超限等）
     * @throws std::runtime_error     OpenSSL 操作失败
     */
    static std::vector<uint8_t> derive(
        const std::vector<uint8_t>& salt,
        const std::vector<uint8_t>& ikm,
        const std::vector<uint8_t>& info,
        size_t length,
        HashAlgo algo = HashAlgo::SHA256
    );

    /**
     * Extract 步骤：提取 PRK
     */
    static std::vector<uint8_t> extract(
        const std::vector<uint8_t>& salt,
        const std::vector<uint8_t>& ikm,
        HashAlgo algo = HashAlgo::SHA256
    );

    /**
     * Expand 步骤：扩展 PRK 至所需长度
     */
    static std::vector<uint8_t> expand(
        const std::vector<uint8_t>& prk,
        const std::vector<uint8_t>& info,
        size_t length,
        HashAlgo algo = HashAlgo::SHA256
    );

    /**
     * 获取底层哈希算法的输出长度（字节）
     */
    static size_t hash_len(HashAlgo algo);

    /**
     * 获取底层哈希算法的块大小（字节）
     */
    static size_t block_size(HashAlgo algo);

private:
    static const EVP_MD* get_evp_md(HashAlgo algo);
    static std::vector<uint8_t> hmac(
        const std::vector<uint8_t>& key,
        const std::vector<uint8_t>& data,
        HashAlgo algo
    );
};

#endif // HKDF_HPP

5.2 实现文件 (`hkdf.cpp`)

#include "hkdf.hpp"

#include <algorithm>
#include <cstring>

const EVP_MD* HKDF::get_evp_md(HashAlgo algo) {
    switch (algo) {
        case HashAlgo::SHA256: return EVP_sha256();
        case HashAlgo::SHA512: return EVP_sha512();
        default: throw std::invalid_argument("Unsupported hash algorithm");
    }
}

size_t HKDF::hash_len(HashAlgo algo) {
    switch (algo) {
        case HashAlgo::SHA256: return 32;
        case HashAlgo::SHA512: return 64;
        default: return 0;
    }
}

size_t HKDF::block_size(HashAlgo algo) {
    switch (algo) {
        case HashAlgo::SHA256: return 64;
        case HashAlgo::SHA512: return 128;
        default: return 0;
    }
}

std::vector<uint8_t> HKDF::hmac(
    const std::vector<uint8_t>& key,
    const std::vector<uint8_t>& data,
    HashAlgo algo
) {
    const EVP_MD* md = get_evp_md(algo);
    std::vector<uint8_t> result(EVP_MAX_MD_SIZE);
    unsigned int result_len = 0;

#if OPENSSL_VERSION_NUMBER >= 0x10100000L && !defined(LIBRESSL_VERSION_NUMBER)
    // OpenSSL 1.1.0+ 使用不透明 HMAC_CTX
    HMAC_CTX* ctx = HMAC_CTX_new();
    if (!ctx) {
        throw std::runtime_error("HMAC_CTX_new failed");
    }

    int ret = HMAC_Init_ex(ctx, key.data(), key.size(), md, nullptr);
    if (ret != 1) {
        HMAC_CTX_free(ctx);
        throw std::runtime_error("HMAC_Init_ex failed");
    }

    ret = HMAC_Update(ctx, data.data(), data.size());
    if (ret != 1) {
        HMAC_CTX_free(ctx);
        throw std::runtime_error("HMAC_Update failed");
    }

    ret = HMAC_Final(ctx, result.data(), &result_len);
    HMAC_CTX_free(ctx);
    if (ret != 1) {
        throw std::runtime_error("HMAC_Final failed");
    }
#else
    // OpenSSL 1.0.x 兼容（不含 LibreSSL 特殊处理可省略）
    HMAC_CTX ctx;
    HMAC_CTX_init(&ctx);
    HMAC_Init_ex(&ctx, key.data(), key.size(), md, nullptr);
    HMAC_Update(&ctx, data.data(), data.size());
    HMAC_Final(&ctx, result.data(), &result_len);
    HMAC_CTX_cleanup(&ctx);
#endif

    result.resize(result_len);
    return result;
}

std::vector<uint8_t> HKDF::extract(
    const std::vector<uint8_t>& salt,
    const std::vector<uint8_t>& ikm,
    HashAlgo algo
) {
    // RFC 5869 2.2: salt 为空时，置为 HashLen 个 0x00
    std::vector<uint8_t> effective_salt = salt;
    if (salt.empty()) {
        effective_salt.assign(hash_len(algo), 0x00);
    }
    return hmac(effective_salt, ikm, algo);
}

std::vector<uint8_t> HKDF::expand(
    const std::vector<uint8_t>& prk,
    const std::vector<uint8_t>& info,
    size_t length,
    HashAlgo algo
) {
    const size_t hlen = hash_len(algo);
    if (prk.size() < hlen) {
        throw std::invalid_argument("PRK length must be at least HashLen");
    }

    const size_t n = (length + hlen - 1) / hlen;  // ceil(length / hlen)
    if (n > 255) {
        throw std::invalid_argument(
            "Requested length exceeds 255 * HashLen"
        );
    }

    std::vector<uint8_t> okm;
    okm.reserve(length);

    // T(0) = 空串
    std::vector<uint8_t> t_prev;

    for (size_t i = 1; i <= n; ++i) {
        // 构建输入: T(i-1) || info || 0x0i
        std::vector<uint8_t> input;
        input.reserve(t_prev.size() + info.size() + 1);
        input.insert(input.end(), t_prev.begin(), t_prev.end());
        input.insert(input.end(), info.begin(), info.end());
        input.push_back(static_cast<uint8_t>(i));

        // T(i) = HMAC-Hash(PRK, input)
        std::vector<uint8_t> t_i = hmac(prk, input, algo);

        okm.insert(okm.end(), t_i.begin(), t_i.end());
        t_prev = std::move(t_i);
    }

    okm.resize(length);
    return okm;
}

std::vector<uint8_t> HKDF::derive(
    const std::vector<uint8_t>& salt,
    const std::vector<uint8_t>& ikm,
    const std::vector<uint8_t>& info,
    size_t length,
    HashAlgo algo
) {
    std::vector<uint8_t> prk = extract(salt, ikm, algo);
    return expand(prk, info, length, algo);
}

5.3 测试向量验证

以下代码验证 RFC 5869 附录 A.1 的测试向量：

#include "hkdf.hpp"
#include <iostream>
#include <iomanip>

void print_hex(const std::vector<uint8_t>& data) {
    for (uint8_t b : data) {
        std::cout << std::hex << std::setw(2) << std::setfill('0')
                  << static_cast<int>(b);
    }
    std::cout << std::dec << std::endl;
}

bool test_rfc5869_case_1() {
    // RFC 5869 A.1: SHA-256 基础测试
    // IKM: 22个 0x0b
    std::vector<uint8_t> ikm(22, 0x0b);

    // salt: 13字节: 0x00,0x01,...,0x0c
    std::vector<uint8_t> salt = {
        0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
        0x08, 0x09, 0x0a, 0x0b, 0x0c
    };

    // info: 0xf0,0xf1,...,0xf9
    std::vector<uint8_t> info = {
        0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9
    };

    size_t L = 42;

    // 预期输出（来自 RFC 5869 A.1）
    std::vector<uint8_t> expected = {
        0x3c, 0xb2, 0x5f, 0x25, 0xfa, 0xac, 0xd5, 0x7a,
        0x90, 0x43, 0x4f, 0x64, 0xd0, 0x36, 0x2f, 0x2a,
        0x2d, 0x2d, 0x0a, 0x90, 0xcf, 0x1a, 0x5a, 0x4c,
        0x5d, 0xb0, 0x2d, 0x56, 0xec, 0xc4, 0xc5, 0xbf,
        0x34, 0x00, 0x72, 0x08, 0xd5, 0xb8, 0x87, 0x18,
        0x58, 0x65
    };

    std::vector<uint8_t> okm = HKDF::derive(
        salt, ikm, info, L, HKDF::HashAlgo::SHA256
    );

    std::cout << "OKM:   ";
    print_hex(okm);
    std::cout << "Expect:";
    print_hex(expected);

    return okm == expected;
}

int main() {
    if (test_rfc5869_case_1()) {
        std::cout << "✓ Test passed" << std::endl;
        return 0;
    } else {
        std::cout << "✗ Test failed" << std::endl;
        return 1;
    }
}

6. 可证明安全分析

6.1 安全假设

HKDF 的安全性建立在两个底层假设之上：

HMAC 是伪随机函数（PRF）：HMAC 实例化为安全哈希函数时，其输出与随机函数在计算上不可区分
输入具有足够熵：IKM（或 salt）至少其一具有不可预测性，使得 Extract 能”浓缩”出均匀分布的 PRK

6.2 定理 1：Extract 的伪随机性

定理陈述：若 HMAC 是 PRF，且 salt 或 IKM 至少其一为高熵随机值，则 HKDF-Extract 输出的 PRK 与均匀随机串在计算上不可区分。

证明思路：

若 salt 为均匀随机密钥，HMAC(salt, IKM) 作为 PRF 直接输出伪随机值
若 IKM 为高熵但 salt 固定，HMAC 的提取器性质保证输出仍然伪随机

量化形式：对任意 PPT 敌手 A，存在可忽略函数 ε(λ)：

|Pr[A(HMAC(salt, IKM)) = 1] - Pr[A(U_HashLen) = 1]| ≤ ε(λ)

6.3 定理 2：Expand 的伪随机性

定理陈述：若 PRK 为均匀随机且 HMAC 为 PRF，则 HKDF-Expand 的输出与长度为 L 的均匀随机串在计算上不可区分。

证明结构：

第一轮：T(1) = HMAC(PRK, info || 0x01) → 因 PRK 随机且 HMAC 为 PRF，T(1) 伪随机
第 i 轮：T(i) = HMAC(PRK, T(i-1) || info || 0x0i) → 由归纳假设 T(i-1) 伪随机，HMAC 再次保证 T(i) 伪随机
计数器 0x0i 确保各轮输入不同，输出彼此独立

6.4 定理 3：密钥独立性

定理陈述：同一 PRK 下，不同 info 派生的密钥在计算上不可区分且相互独立。

依据：Expand 每轮将 info 作为 HMAC 输入的一部分。由于 HMAC 为 PRF，HMAC(PRK, ·) 在不同输入上的输出可视为独立随机值。因此，不同 info 派生的密钥间无计算上可探测的相关性。

6.5 局限性：dual-PRF 假设的争议

部分协议（如 TLS 1.3）在使用 HKDF 时隐式假设 HMAC 具有dual-PRF安全性——即交换 HMAC 的两个输入后仍保持 PRF 安全性。然而：

HMAC 在底层哈希函数具有碰撞时不满足 dual-PRF 性质
目前尚无证明表明碰撞抵抗性足以推导 HMAC 的 dual-PRF 安全性
在 salt 可能被敌手影响的场景下（如密钥组合），需额外谨慎

安全规约图：

底层假设层
├── 压缩函数是 PRF（Bellare 2006）
│   └── → HMAC 是 PRF
├── 或：压缩函数是弱 PRF + 加盐（Fischlin 2018）
│   └── → 加盐 HMAC 仍为 PRF
└── ─────────────────────
                ↓
HMAC 层：HMAC 是 PRF（标准假设）
                ↓
HKDF 层：
├── Extract：IKM 或 salt 有熵 → PRK 伪随机（Krawczyk 2010）
├── Expand：PRK 随机 + HMAC 为 PRF → OKM 伪随机
└── 注意：dual-PRF 假设未获可证明支持

7. 引用

Fischlin, M. et al. (2018). Backdoored Hash Functions: Immunizing HMAC and HKDF. CSF 2018.

Krawczyk, H., Eronen, P. (2010). HMAC-based Extract-and-Expand Key Derivation Function (HKDF). RFC 5869.

Hoang, D.L. et al. (2025). New proofs for pseudorandomness of HMAC-based key derivation functions (RFC 5869). IACR ePrint 2025/657.

Krawczyk, H. (2010). Cryptographic Extraction and Key Derivation: The HKDF Scheme. CRYPTO 2010.

Bellare, M. (2006). New Proofs for NMAC and HMAC: Security without Collision-Resistance. CRYPTO 2006.

IETF RFC 5869 Test Vectors.

HKDF：算法规范、C++11实现与可证明安全分析

1. 概述

2. 符号约定

3. 算法规范

3.1 HKDF-Extract

3.2 HKDF-Expand

3.3 HKDF 组合函数

4. 参数使用规范

4.1 salt（盐值）

4.2 info（上下文信息）

4.3 跳过 Extract 的适用场景

5. C++11 完整实现

5.1 头文件 (`hkdf.hpp`)

5.2 实现文件 (`hkdf.cpp`)

5.3 测试向量验证

6. 可证明安全分析

6.1 安全假设

6.2 定理 1：Extract 的伪随机性

6.3 定理 2：Expand 的伪随机性

6.4 定理 3：密钥独立性

6.5 局限性：dual-PRF 假设的争议

7. 引用

老丹

其他文章

守护数字世界的隐形之盾：TLS/SSL完全解剖指南

安全传输层协议（TLS）全貌解析

HKDF：算法规范、C++11实现与可证明安全分析

1. 概述

2. 符号约定

3. 算法规范

3.1 HKDF-Extract

3.2 HKDF-Expand

3.3 HKDF 组合函数

4. 参数使用规范

4.1 salt（盐值）

4.2 info（上下文信息）

4.3 跳过 Extract 的适用场景

5. C++11 完整实现

5.1 头文件 (hkdf.hpp)

5.2 实现文件 (hkdf.cpp)

5.3 测试向量验证

6. 可证明安全分析

6.1 安全假设

6.2 定理 1：Extract 的伪随机性

6.3 定理 2：Expand 的伪随机性

6.4 定理 3：密钥独立性

6.5 局限性：dual-PRF 假设的争议

7. 引用

老丹

其他文章

守护数字世界的隐形之盾：TLS/SSL完全解剖指南

安全传输层协议（TLS）全貌解析

5.1 头文件 (`hkdf.hpp`)

5.2 实现文件 (`hkdf.cpp`)