Introduction
In the world of cryptanalysis, papers typically celebrate the successful "breaking" of a cipher. However, "Row, Row, Row Your Boat" offers a refreshing and humorous departure: a high-effort cautionary tale about a failed attack. This "negative result" provides invaluable lessons on implementation details and the necessity of early assumption verification.
The Pilsung Cipher and the Weak Key Hypothesis
Pilsung is a block cipher found within North Korea’s Red Star operating system. While heavily based on the Advanced Encryption Standard (AES), it replaces the fixed ShiftRows operation with a key-dependent permutation. A report by Kryptos Logic hypothesized that this design might contain a "backdoor": if a key is chosen such that the permutation fails to move bytes between columns, diffusion is crippled. This would theoretically allow an attacker to break the encryption using differential cryptanalysis.
Methodology: Hunting for Weak Keys
The researchers employed a multi-step approach to identify these elusive weak keys:
- Shuffle Analysis: They analyzed the Rao-Sandelius shuffle used by Pilsung, finding it produces only a fraction of possible permutations ($2^{36.7}$), making a search feasible.
- Search Algorithm: They developed a "meet-in-the-middle" strategy to find keys resulting in column-preserving permutations.
- Differential Distinguishers: They designed a method to distinguish weak keys by injecting a single-byte difference into the plaintext. For a weak key, the resulting ciphertext difference should remain confined to fewer bytes than for a strong key.
The Implementation Trap: Row vs. Column
After burning through over 10,000 CPU hours on the University of Adelaide’s "Phoenix" cluster, the researchers reached a startling realization: their attack had failed due to a fundamental misunderstanding of data structures.
They had assumed the 16-byte state of the cipher was stored in row-first order. However, Pilsung—following the AES standard—uses column-first order. Consequently, the researchers had spent thousands of hours finding keys that preserved rows instead of columns. Because the MixColumns step only mixes data within a column, preserving rows does nothing to weaken the cipher. In fact, standard AES is designed to preserve rows during its ShiftRows step.
Results and Lessons Learned
The optimized search tool was technically impressive, exploring roughly $2^{25}$ keys per core per second. However, the ultimate result was a humorous financial calculation: had the 10,000 CPU hours been spent mining Bitcoin, the team would have earned approximately $7.91.
The authors conclude that the specific class of weak keys they sought likely does not exist in Pilsung, as the shuffle randomness ensures sufficient column mixing. The primary takeaway is the importance of a "fail-fast" approach. Researchers should verify attacks on round-reduced versions of a cipher before committing massive resources. This simple step would have revealed the row/column misunderstanding in minutes, saving months of wasted computation.
Summary updated