Kỹ thuật phát hiện hàm băm số nguyên tự động

Hash Function Prospector

Công cụ này là một tiện ích nhỏ nhằm tự động khám phá hàm băm số nguyên. Nó tạo ra hàng tỷ hàm băm số nguyên bằng cách chọn ngẫu nhiên trong 9 phép biến đổi khả nghịch. Các hàm đã tạo được biên dịch JIT và hành vi Avalanche được đánh giá. Hiện tại, hàm tốt nhất sẽ được xuất dưới cú pháp C.

• Điểm Avalanche: số bit đầu ra trung bình giữ nguyên khi lật một bit đầu vào duy nhất. Điểm càng thấp càng tốt. Lý tưởng nhất là 0; tức là khi lật một bit đầu vào thì mọi bit đầu ra đều có xác suất 50% bị đảo.
• Prospector có thể tạo cả hàm băm số nguyên 32-bit và 64-bit. Kiểm tra tùy chọn đầy đủ trong hướng dẫn sử dụng (-h). Do trình biên dịch JIT nên chỉ hỗ trợ x86-64, nhưng các hàm đã được phát hiện có thể dùng ở mọi nơi.

Các hàm băm đã phát hiện

Có hai lớp hàm băm hữu ích đã được phát hiện bởi Prospector và các tiện ích phụ trợ khác ở đây. Cả hai đều dùng cấu trúc xorshift-multiply-xorshift, nhưng khác nhau ở số vòng.

Hàm 2 vòng

TheIronBorn đã dùng tối ưu hóa tổ hợp để tìm các tham số tốt nhất đã biết cho cấu trúc này.

• 2-vòng hoán vị 32-bit này có mức thiên lệch rất thấp, thậm chí còn thắng tiny hơn với finalizer 32-bit nổi tiếng của MurmurHash3.
• Cấu trúc hàm băm này được phát hiện bởi Prospector, các tham số được tinh chỉnh bằng hill climbing và thuật toán di truyền.

Có nhiều hằng số 2 vòng thiên lệch thấp hơn, trong đó một số còn tốt hơn lowbias32.

Hàm 3 vòng

Thêm thêm một vòng multiply-xorshift vào cấu trúc này có thể đạt tới giới hạn thiên lệch lý thuyết với tham số được chọn cẩn trọng. Chẳng hạn, hàm băm này không thể phân biệt với một PRF hoàn hảo.

• triple32 không chỉ khắc phục vấn đề hash(0) = 0, mà còn giảm thêm thiên lệch.
• Có thêm nhiều hằng số 3 vòng thiên lệch thấp hơn.

Đo thiên lệch chính xác

Chế độ -E đánh giá thiên lệch của một hàm băm cụ thể (-p hoặc -l). Mặc định, Prospector dùng các ước lượng để đánh giá nhanh thiên lệch hàm, nhưng các kết quả có tính nhiễu cao và phi quyết định. Dùng tùy chọn -e để đo thiên lệch chính xác một cách toàn diện.

• Có thể định nghĩa hàm cần kiểm tra bằng -p và pattern, hoặc với một thư viện dùng chung chứa hàm hash() kết hợp -l.
• Kiểm thử đầy đủ chính xác cho hàm băm 64-bit không có vì sẽ tốn quá nhiều thời gian.

Lựa chọn phép biến đổi khả nghịch

Sử dụng các phép biến đổi khả nghịch sau:

• x = ~x;
• x ^= constant;
• x *= constant | 1; (chỉ hằng số lẻ)
• x += constant;
• x ^= x >> constant;
• x ^= x << constant;
• x += x << constant;
• x -= x << constant;
• x <<<= constant; (xoay trái)
• x = bswap(x) (đổi chỗ byte cao và byte thấp)

Về mặt kỹ thuật, x = ~x đã được bao phủ bởi x ^= constant; tuy nhiên, ~x khá đặc biệt và đặc biệt hữu ích.

Băm 16-bit

Vì ràng buộc khác nhau của băm 16-bit, nên có một công cụ riêng hp16 để sinh các hàm băm này.

• Khác với Prospector 32-bit/64-bit, bản triển khai này hoàn toàn portable và chạy được trên gần như mọi hệ thống.
• Có thể tạo và đánh giá S-box 128KiB.
• Băm 16-bit có thể cần thiết hơn trên máy không có lệnh nhân nhanh, nên có thể bỏ qua một số phép toán khi dò tìm (-m, -r).

Một số kết quả thú vị:

• Băm xorshift-multiply 2 vòng
• Băm xorshift-multiply 3 vòng
• Băm không dùng nhân (chỉ dùng xorshift-add)

Một băm xorshift 3 vòng tốt (hp16 -Xn3 qua tìm kiếm ngắn) đã tiệm cận một S-box tốt (hp16 -S).

Khi làm việc với phép toán 16-bit, cần chú ý quy tắc mở rộng kiểu nguyên của C. Chương trình C được công cụ này xuất ra luôn để ý đến việc nâng cấp phép toán 16-bit sang unsigned int khi cần.

Ý kiến của GN⁺

• An toàn của hàm băm có vai trò rất quan trọng trong mật mã học và bảo mật máy tính, nên các công cụ dò tìm như vậy rất có tiềm năng cho nghiên cứu. Đặc biệt, việc tìm ra hàm băm có thiên lệch thấp bằng tìm kiếm ngẫu nhiên rất đáng chú ý.

• Tuy nhiên, an toàn của hàm băm không thể bảo đảm chỉ bằng đặc tính thống kê. Hàm băm mật mã cần an toàn trước các tấn công như PreImage Resistance, Second PreImage Resistance, Collision Resistance..., nên cần phân tích thêm các khía cạnh này.

• Băm 16-bit có vẻ hữu dụng trong các môi trường hạn chế như IoT hoặc hệ thống nhúng. Ấn tượng ở chỗ có thể tạo hàm băm dùng chỉ ADD/XOR/SHIFT để chạy được cả trên CPU không có lệnh nhân.

• Việc áp dụng các kỹ thuật tìm kiếm heuristic như Hill Climbing hoặc thuật toán di truyền vào thiết kế hàm băm cũng là ý tưởng mới mẻ. Khi việc áp dụng AI vào thiết kế thuật toán mật mã đang ngày càng mạnh, các kỹ thuật tối ưu hóa như vậy có thể sẽ đóng vai trò quan trọng hơn.

• Tuy nhiên, do giới hạn của hàm băm, dù Avalanche có tốt đến đâu thì cũng khó khẳng định đây là an toàn về mật mã; đây có lẽ là hạn chế của dự án này. Dù vậy, công cụ như vậy vẫn có thể giúp phân tích và cải thiện các điểm yếu của các hàm băm hiện có.

[GN⁺]

Ý kiến trên Hacker News

• Lý do thích mã của nhà phát triển này
  • Thích thư viện JSON, thư viện phân tích tùy chọn, trình giải mã UTF-8 không có nhánh, stack không khóa và thư viện trie
  • Thích việc tất cả các thư viện trên đều được công bố theo Unlicense
• Nhận xét của nhà phát triển MurmurHash
  • Ghi nhận rằng phép toán multiply-shift-xor đã tồn tại bền bỉ từ lâu là điều thú vị
• Chia sẻ về ý tưởng tìm kiếm hàm băm tự động
  • Nên tích hợp với SMHasher3 để tự động đánh giá kết quả
    • Có thể dùng một số test nhất định để tăng tốc và loại bỏ nhanh hơn
  • Có lẽ cũng tốt nếu mở rộng sang hàm băm 64-bit và 128-bit (dù không gian tìm kiếm lớn hơn)
  • Đã tạo mã NodeJS trong thư viện Rain để đo hiệu ứng avalanche khi nhân với số nguyên tố 64-bit
• Chia sẻ kinh nghiệm triển khai bài toán 1brc bằng Go
  • Đã thử tìm một hàm băm hoàn hảo tùy chỉnh để đặt mỗi nhà ga vào một bucket riêng mà không đụng nhau, nhưng đã bỏ cuộc vì quy tắc cấm tùy chỉnh hàm băm theo dữ liệu trước khi chương trình bắt đầu chạy
  • Đã tạo một công cụ kiểm tra: lấy hằng số ngẫu nhiên và in ra hằng số tốt nhất hiện có theo số bucket đụng nhau cùng tổng số va chạm
    • Đã giảm xuống còn 1 bucket có chỉ 2 va chạm với mức lấp đầy khoảng 40%
    • Điều thú vị là những giá trị tương tự về số vị trí nhảy được đưa vào đều nằm trong hằng số hiệu năng tốt nhất, bất kể các hằng số khác
• Yêu cầu giải thích vì sao đoạn mã này hay và dùng để làm gì
• Tò mò về việc đoạn mã đang làm gì chính xác: liệu có phải đang tìm hàm băm tốt nhất không, và nếu không thì tại sao hàm băm tốt nhất lại thay đổi mỗi lần chạy
• Xin thông tin về cơ chế để tìm hàm băm tốt cho các giá trị nguyên trong một phạm vi cố định
  • Ví dụ: biết các giá trị nguyên từ 10.000 đến 200.000 và muốn băm chúng vào số lượng bucket tối ưu
• Ý kiến cho rằng giới hạn ở phép toán khả nghịch có điểm mạnh toán học nhưng loại bỏ rất nhiều khả năng
  • Đã nghĩ về việc băm hoàn hảo khi đã biết trước tập đầu vào
  • Thông thường dùng mảng hằng số, nhưng nếu đầu vào đã là số nguyên nhỏ thì muốn biết liệu có thể nén hơn nữa không
  • Đã liệt kê khoảng 100 phép toán cơ bản, nhưng chán nên không tiếp tục dự án
• Nếu dùng cùng một hằng số cho cả hai phép nhân, có thể giảm kích thước mã nên tốc độ tính toán hơi nhanh hơn
• Dù thừa nhận các hàm này không phù hợp cho cryptography, vẫn đặt câu hỏi về tác động của "độ lệch" đã đo tới phân tích mật mã
  • Tò mò liệu ai quen thuộc với mật mã sai biệt có thể giải thích được không
  • Hỏi liệu hàm băm có độ lệch thấp có thể làm vô hiệu hóa phân tích mật mã với số vòng hoặc tính toán ít hơn không
  • Hỏi liệu công cụ này có thể hữu ích trong việc tìm hàm băm mật mã tốt hơn hay không
• Giới thiệu một dự án tương tự
  • Chậm hơn (do dùng interpreter) nhưng chất lượng hàm tốt hơn
  • Tuy nhiên, vẫn chưa tìm thấy giải pháp tốt hơn các hàm băm hiện có