băm phản xạ?

Question

Có một lớp học của các thuật toán băm, cho dù lý thuyết hay thực tiễn, như vậy mà một algo trong lớp có thể được coi là 'phản' Theo một định nghĩa đưa ra dưới đây:

• hash1 = algo1 ("nhập văn bản 1")
• hash1 = algo1 ("text input 1" + hash1)

toán tử + có thể nối hoặc bất kỳ hoạt động quy định khác để kết hợp các đầu ra (hash1) trở lại vào đầu vào ("nhập văn bản 1") để thuật toán (algo1) sẽ tạo ra kết quả tương tự. tức là xung đột trên đầu vào và đầu vào + đầu ra. Toán tử + phải kết hợp toàn bộ cả hai đầu vào và bản ngã có thể không loại bỏ một phần của đầu vào.

Thuật toán phải tạo 128 bit entropy trong đầu ra. Nó có thể, nhưng không cần, phải khó mã hóa để đảo ngược đầu ra trở lại một hoặc cả hai đầu vào có thể.

Tôi không phải là nhà toán học, nhưng câu trả lời hay có thể bao gồm bằng chứng về lý do tại sao một lớp thuật toán không thể tồn tại. Tuy nhiên, đây không phải là một câu hỏi trừu tượng. Tôi thực sự quan tâm đến việc sử dụng một thuật toán như vậy trong hệ thống của tôi, nếu một trong những tồn tại.

Answer 1

Vâng, tôi có thể cho bạn biết rằng bạn sẽ không nhận được bằng chứng về sự không tồn tại. Dưới đây là ví dụ:

toán tử + (a, b): tính toán băm 64 bit của a, băm 64 bit của b và nối các bitstray, trả về băm 128 bit.

algo1: đối với một số giá trị 128-bit, bỏ qua 64 bit cuối cùng và tính toán một số hash của người đầu tiên 64.

chính thức, bất kỳ algo1 rằng sản lượng các nhà điều hành đầu tiên + như là bước đầu tiên của mình sẽ làm. Có lẽ không phải là một lớp học thú vị như bạn đang tìm kiếm, nhưng nó phù hợp với dự luật. Và nó không phải không có các trường hợp trong thế giới thực. Rất nhiều thuật toán băm mật khẩu cắt ngắn đầu vào của chúng.

Answer 2

Tôi khá chắc chắn rằng một hàm băm "phản xạ" (nếu nó tồn tại nhiều hơn ý nghĩa tầm thường) sẽ không phải là hàm băm hữu ích theo nghĩa thông thường.

Đối với một ví dụ về một hàm băm "tầm thường" phản:

int hash(Object obj) { return 0; } 

Answer 3

Chắc chắn, đây là một cách khá thông thường:

def algo1(input): 
    sum = 0 
    for i in input: 
     sum += ord(i) 
    return chr(sum % 256) + chr(-sum % 256) 

CONCATENATE kết quả và "băm" không thay đổi. Nó khá dễ dàng để đến với một cái gì đó tương tự khi bạn có thể đảo ngược băm.

Answer 4

xây dựng trên ephemiat's answer, tôi nghĩ bạn có thể làm điều gì đó như thế này:

Pick yêu thích đối xứng khối mật mã chìa khóa của bạn (ví dụ .: AES). Để cụ thể, hãy nói rằng nó hoạt động trên các khối 128 bit. Đối với một khóa K, biểu thị hàm mã hóa và hàm giải mã bằng Enc (K, block) và Dec (K, block), tương ứng, sao cho khối = Dec (K, Enc (K, block)) = Enc (K, Tháng mười hai (K, khối)).

Chia đầu vào của bạn thành một mảng các khối 128 bit (đệm khi cần thiết). Bạn có thể chọn một khóa cố định K hoặc biến nó thành một phần của đầu vào thành băm. Trong phần tiếp theo, chúng tôi sẽ giả định rằng nó đã được sửa.

def hash(input): 
    state = arbitrary 128-bit initialization vector 
    for i = 1 to len(input) do 
     state = state^Enc(K, input[i]) 
    return concatenate(state, Dec(K, state)) 

Hàm này trả về giá trị băm 256 bit. Nó sẽ không quá khó để xác minh rằng nó đáp ứng các điều kiện "phản xạ" với một caveat - đầu vào phải được đệm vào một số toàn bộ khối 128-bit trước khi băm được nối liền. Nói cách khác, thay vì hash (input) = hash (input + hash (input)) như được chỉ định ban đầu, chúng ta có hash (input) = hash (input '+ hash (input)) trong đó input' chỉ là input độn. Tôi hy vọng điều này không quá nguy hiểm.

Answer 5

Có, bạn có thể nhận được hiệu ứng này với CRC.

Những gì bạn cần làm là:

1. Thực hiện một thuật toán sẽ tìm thấy một chuỗi các bit đầu vào N hàng đầu từ một trạng thái nhất định (của N-bit CRC ắc) khác.
2. Tính CRC của đầu vào theo cách thông thường. Lưu ý trạng thái cuối cùng (gọi là A)
3. Sử dụng hàm được thực hiện trong (1), tìm một chuỗi các bit dẫn từ A đến A. Chuỗi này là mã băm của bạn. Bây giờ bạn có thể gắn nó vào đầu vào.

[Initial state] >- input string -> [A] >- hash -> [A] ... 

Here is one way to find the hash. (Lưu ý: có lỗi trong các số trong ví dụ CRC32, nhưng thuật toán hoạt động.)

Và đây là một triển khai trong Java. Lưu ý: Tôi đã sử dụng CRC 32 bit (nhỏ hơn 64 bạn chỉ định) vì được triển khai trong thư viện chuẩn, nhưng với mã thư viện của bên thứ ba, bạn có thể dễ dàng mở rộng nó thành các băm lớn hơn.

public static byte[] hash(byte[] input) { 
    CRC32 crc = new CRC32(); 
    crc.update(input); 
    int reg = ~ (int) crc.getValue(); 
    return delta(reg, reg); 
} 

public static void main(String[] args) { 
    byte[] prefix = "Hello, World!".getBytes(Charsets.UTF_8); 

    System.err.printf("%s => %s%n", Arrays.toString(prefix), Arrays.toString(hash(prefix))); 

    byte[] suffix = hash(prefix); 
    byte[] combined = ArrayUtils.addAll(prefix, suffix); 

    System.err.printf("%s => %s%n", Arrays.toString(combined), Arrays.toString(hash(combined))); 
} 

private static byte[] delta(int from, int to) { 
    ByteBuffer buf = ByteBuffer.allocate(8); 
    buf.order(ByteOrder.LITTLE_ENDIAN); 
    buf.putInt(from); 
    buf.putInt(to); 
    for (int i = 8; i-- > 4;) { 
     int e = CRCINVINDEX[buf.get(i) & 0xff]; 
     buf.putInt(i - 3, buf.getInt(i - 3)^CRC32TAB[e]); 
     buf.put(i - 4, (byte) (e^buf.get(i - 4))); 
    } 
    return Arrays.copyOfRange(buf.array(), 0, 4); 
} 
private static final int[] CRC32TAB = new int[0x100]; 
private static final int[] CRCINVINDEX = new int[0x100]; 
static { 
    CRC32 crc = new CRC32(); 
    for (int b = 0; b < 0x100; ++ b) { 
     crc.update(~b); 
     CRC32TAB[b] = 0xFF000000^(int) crc.getValue(); 
     CRCINVINDEX[CRC32TAB[b] >>> 24] = b; 
     crc.reset(); 
    } 
}