No Difference

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-22 | Status: Solved Techniques: non_injective_sbox_collision, repeated_sbox_value_detection, single_block_brute_force

Summary

Task: a custom block hash declares a winning flag if you supply two distinct inputs with the same hash. Solution: permute() is a GF(2) bit-transpose (linear, involution, bijective) so it loses no information; substitute() maps each byte through an SBOX that has repeated values, making it non-injective. A trivial brute over 4-byte single blocks finds two distinct inputs colliding almost instantly (00500000 vs 00590000), submitted as fields a,b to port 13395.

No Difference — cryptohack (Hashes)

Description

"The difference between treason and patriotism is only a matter of dates."

Server socket.cryptohack.org:13395 takes two hex inputs a, b (each a multiple of 4 bytes) and returns the flag iff a != b but hash(a) == hash(b):

 python read-only • copy allowed Copy
SBOX = [0xf0,0xf3,0xf1,0x69, ... ]    # 256 entries, but with REPEATED values

def permute(block):                    # GF(2) bit-transpose of an 8x8 bit matrix
    result = [0]*8
    for i in range(8):
        x = block[i]
        for j in range(8):
            result[j] |= (x & 1) << i
            x >>= 1
    return result
# permute(permute(x)) == x  and  permute(a)^permute(b) == permute(a^b)  -> linear involution
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def substitute(block): return [SBOX[x] for x in block]

def hash(data):
    if len(data) % 4 != 0: return None
    state = [16,32,48,80,80,96,112,128]
    for i in range(0, len(data), 4):
        block = data[i:i+4]
        state[4]^=block[0]; state[5]^=block[1]; state[6]^=block[2]; state[7]^=block[3]
        state = permute(state); state = substitute(state)
    for _ in range(16):
        state = permute(state); state = substitute(state)
    output = []
    for _ in range(2):
        output += state[4:]; state = permute(state); state = substitute(state)
    return bytes(output)

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

We need any collision. Look at the two primitives:

• permute is a bit-transpose over GF(2): it treats the 8-byte state as an 8x8 bit matrix and transposes it. The source even documents permute(permute(x)) == x (involution) and permute(a)^permute(b) == permute(a^b) (linear). A transpose is a bijection — it loses no information.

• substitute applies SBOX byte-wise. The whole point: this SBOX table contains repeated values (e.g. 0xf3 appears multiple times, 0x9b, 0xbe, etc.). A lookup table with repeats is not injective — two different inputs can map to the same output. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Since the only non-linear / lossy step is the non-injective S-box, the entire hash is non-injective and collisions are dense. For a single 4-byte block, the processing is: state[4:8] ^= block, then permute, then substitute, then 16 finishing rounds and output. The initial state bytes 0-3 are constant; only bytes 4-7 absorb block. Because substitute collapses distinct bytes that share an SBOX value, two blocks that differ only where the S-box folds them together produce the same hash. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

So we don't need to be clever — just brute a tiny corner of the single-block input space and a collision pops out almost immediately.

Solution

Brute over the first two bytes of a single 4-byte block (full solver solve_nodiff.py):

 python read-only • copy allowed Copy
seen = {}
for x in range(256):
    for y in range(256):
        blk = bytes([x, y, 0, 0])
        h = hash(blk)
        if h in seen and seen[h] != blk:
            print("COLLISION", seen[h].hex(), blk.hex(), h.hex())
            # -> 00500000  vs  00590000
            raise SystemExit
        seen[h] = blk

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

This finds 00500000 and 00590000 (bytes 0x50 and 0x59 collapse to the same S-box output in this position), both hashing to the same value. Submit them as the two fields:

 python read-only • copy allowed Copy
send({"a": "00500000", "b": "00590000"})     # distinct -> same hash -> flag

Takeaways

Use this technique when:

• A custom hash/cipher's only "confusion" step is an S-box (lookup table) with repeated entries — it is non-injective, so collisions exist and are easy to brute over a small input window.
• The "diffusion" step is a linear bijection (bit-transpose, matrix multiply, permutation) — it cannot create or destroy collisions, so all collision behaviour comes from the S-box.
• A challenge only asks for a collision (not a specific target): try the smallest input unit (single block, vary 1-2 bytes) before any structured/differential attack — the S-box folding usually yields a collision within a few thousand evaluations. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍