安全平等:为什么不平等仍然持续时间较短？

Question

我有一个比较两个字节数组是否相等的方法,主要的警告是它不会失败并在检测到不等式时提前退出.基本上,代码用于比较跨站请求伪造令牌,并尽可能避免使用时间来破解密钥的能力.我希望我能找到详细讨论攻击的论文的链接,但重要的是,如果两个字节数组相等,我仍然有一个统计上可测量的偏差,以便尽快返回 - 尽管它是一个命令更好的.所以不用多说,这里是代码:

public static bool SecureEquals(byte[] original, byte[] potential)
{
    // They should be the same size, but we don't want to throw an
    // exception if we are wrong.
    bool isEqual = original.Length == potential.Length;
    int maxLenth = Math.Max(original.Length, potential.Length);

    for(int i=0; i < maxLength; i++)
    {
        byte originalByte = (i < original.Length) ? original[i] : (byte)0;
        byte potentialByte = (i < potential.Length) ? potential[i] : (byte)0;

        isEqual = isEqual && (originalByte == potentialByte);
    }

    return isEqual;
}

对于不等标记,相等和不等标记之间的平均时间差异始终为10-25ms(取决于垃圾收集周期).这正是我想要避免的.如果相对时间相等,或者根据运行交换的平均时间我会很高兴.问题是我们对于不等标记的持续时间越来越短.相反,如果我们在第一个不相等的令牌上停止循环,我们的时间差异最多可达80倍.

虽然这种平等检查是典型的急切回报的重大改进,但仍然不够好.从本质上讲,我不希望任何一致的结果导致平等或不平等更快地返回.如果我可以将结果放到垃圾收集周期掩盖任何一致偏差的范围内,我会很高兴.

任何人都有一个线索是什么导致不平等的时间偏差更快？起初我以为是三元运算符返回对数组的访问,如果数组的大小不等,则返回常量.问题是,如果两个阵列的大小相同,我仍会得到这种偏见.

注意:根据要求,指向时间攻击的文章的链接:

• http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf(官方文件,链接到下面的博客文章)
• http://codahale.com/a-lesson-in-timing-attacks/ (谈论Java库中的失败)
• http://en.wikipedia.org/wiki/Timing_attack(更一般,但不完整)

Answer 1

这条线可能会导致问题:

isEqual = isEqual && (originalByte == potentialByte);

originalByte == potentialByte如果isEquals已经为假,则不会费心评估子表达式.您不希望在此处使用短路,因此请将其更改为:

isEqual = isEqual & (originalByte == potentialByte);

编辑:请注意,您已经有效地泄露了有关原始数据大小的信息 - 因为它总是在一个恒定的时间内运行,直到potential数组超出original数组大小,此时时间会增加.避免这种情况可能相当棘手......因此,我会选择"如果它们的尺寸不合适则抛出异常",并明确承认它.

编辑:只是为了回顾我在评论中包含的想法:

// Let's assume you'll never really need more than this
private static readonly byte[] LargeJunkArray = new byte[1024 * 32];

public static bool SecureEquals(byte[] original, byte[] potential)
{
    // Reveal that the original array will never be more than 32K.
    // This is unlikely to be particularly useful.
    if (potential.Length > LargeJunkArray.Length)
    {
        return false;
    }
    byte[] copy = new byte[potential.Length];
    int bytesFromOriginal = Math.Min(original.Length, copy.Length);
    // Always copy the same amount of data
    Array.Copy(original, 0, copy, 0, bytesFromOriginal);
    Array.Copy(LargeJunkArray, 0, copy, bytesFromOriginal,
               copy.Length - bytesFromOriginal);

    bool isEqual = original.Length == potential.Length;
    for(int i=0; i < copy.Length; i++)
    {
        isEqual = isEqual & (copy[i] == potential[i]);
    }

    return isEqual;
}

请注意,这假设Array.Copy从任何来源复制相同数量的数据将花费相同的时间 - 这可能不是真的,基于CPU缓存......