彩虹表与查表攻击

概念概述

彩虹表与查表攻击（Rainbow Tables and Lookup Attacks）指的是：彩虹表以存储与计算换取对未加盐哈希的逆向，因此口令存储需要每用户随机盐，并配合缓慢的哈希算法。

从更严格的定义看，A rainbow table is a precomputed structure that maps hash values back to likely plaintexts, allowing an attacker with a stolen hash to recover short or common passwords quickly. 该概念在工程实践中的价值，在于它能帮助团队用统一的语言描述一个具体的质量属性或设计约束，从而在评审与协作中减少歧义。

为什么需要它

It is the reason unsalted, fast hashes are unfit for password storage and why a unique salt per user is mandatory. 它与 Password Salting、Authenticated Encryption (AEAD)、Forward Secrecy 等概念经常一起出现，用于解决相近的工程问题。理解它的适用场景，有助于在多种备选方案之间做出有依据的取舍，而不是凭直觉选择技术方案。

常见误解

• rainbow tables work against any hash regardless of salt
• a longer password always defeats a rainbow table attack

需要避免的反模式

• storing plain hashes of passwords in a single shared column
• assuming a fast general-purpose hash is adequate for credentials

实践要点

1. The table encodes many candidate inputs and their hashes with a time-memory trade-off, so reversing a hash becomes a lookup rather than a brute-force search.
2. A unique random salt per password makes the same plaintext hash differently for every user, which invalidates any single precomputed table across the dataset.
3. Salt defeats precomputation but not guessing, so it is paired with a deliberately slow, memory-hard algorithm that raises the cost of each attempt.

参考来源

https://owasp.org/www-community/attacks/Rainbow_table

代码示例

import hashlib
import hmac
import os

N = 2 ** 14
R = 8
P = 1
KEY_LEN = 32
SALT_LEN = 16

def hash_password(password: str) -> str:
    salt = os.urandom(SALT_LEN)
    digest = hashlib.scrypt(password.encode('utf-8'), salt=salt, n=N, r=R, p=P, dklen=KEY_LEN)
    return f'scrypt${N}${R}${P}${salt.hex()}${digest.hex()}'

def verify_password(password: str, encoded: str) -> bool:
    parts = encoded.split('$')
    if len(parts) != 5 or parts[0] != 'scrypt':
        return False
    _, n, r, p, rest = parts
    salt_hex, digest_hex = rest[:SALT_LEN * 2], rest[SALT_LEN * 2:]
    expected = bytes.fromhex(digest_hex)
    digest = hashlib.scrypt(password.encode('utf-8'), salt=bytes.fromhex(salt_hex),
                            n=int(n), r=int(r), p=int(p), dklen=len(expected))
    return hmac.compare_digest(digest, expected)

import { createCipheriv, createDecipheriv, randomBytes, scryptSync } from "node:crypto";

const ALGORITHM = "aes-256-gcm";

export interface EncryptedPayload {
  salt: string;
  iv: string;
  tag: string;
  data: string;
}

export function deriveAesKey(passphrase: string, salt: Buffer): Buffer {
  if (typeof passphrase !== "string" || passphrase.length < 12) {
    throw new RangeError("passphrase must be at least 12 characters");
  }
  return scryptSync(passphrase.normalize("NFKC"), salt, 32);
}

export function encryptString(plaintext: string, passphrase: string): EncryptedPayload {
  const salt = randomBytes(16);
  const iv = randomBytes(12);
  const cipher = createCipheriv(ALGORITHM, deriveAesKey(passphrase, salt), iv);
  const data = Buffer.concat([cipher.update(plaintext, "utf8"), cipher.final()]);
  return {
    salt: salt.toString("base64"),
    iv: iv.toString("base64"),
    tag: cipher.getAuthTag().toString("base64"),
    data: data.toString("base64"),
  };
}

export function decryptString(payload: EncryptedPayload, passphrase: string): string {
  const salt = Buffer.from(payload.salt, "base64");
  const iv = Buffer.from(payload.iv, "base64");
  const tag = Buffer.from(payload.tag, "base64");
  const decipher = createDecipheriv(ALGORITHM, deriveAesKey(passphrase, salt), iv);
  decipher.setAuthTag(tag);
  return Buffer.concat([
    decipher.update(Buffer.from(payload.data, "base64")),
    decipher.final(),
  ]).toString("utf8");
}