Source-linked AI summary
SOSEMANUK: a fast software-oriented stream cipher
Come Berbain, Olivier Billet, Anne Canteaut, Nicolas Courtois, Henri Gilbert, Louis Goubin, Aline Gouget, Louis Granboulan, Cedric Lauradoux, Marine Minier, Thomas Pornin, Herve Sibert
TL;DR
The paper addresses the design of a software-oriented stream cipher seeking improved security and efficiency relative to SNOW 2.0. It proposes Sosemanuk, combining SNOW 2.0 principles with SERPENT-derived transformations and a reduced-state design. The cipher supports 128- to 256-bit keys, with 128-bit security claimed for all variants, while reducing static data and improving initialization.
Problem
The paper seeks a software-oriented stream cipher that avoids potential structural weaknesses of SNOW 2.0 while improving efficiency across architectures.
Method
Sosemanuk combines SNOW 2.0 design principles with SERPENT-derived transformations, using a shorter LFSR, reduced static data, and SERPENT-based initialization.
Results
Sosemanuk supports 128- to 256-bit keys with claimed 128-bit security for every key length, while its static data is 3 times smaller than SNOW 2.0's.
Takeaways & Limitations
The design provides a software-oriented cipher with reduced state and static-data requirements, alongside a key setup based on a reduced version of SERPENT.
Takeaways & Limitations
The 128-bit security claim excludes attackers benefiting from large precomputation, and longer keys do not raise the claimed security level above 128 bits.
Abstract
from arXiv · showhide
Sosemanuk is a new synchronous software-oriented stream cipher, corresponding to Profile 1 of the ECRYPT call for stream cipher primitives. Its key length is variable between 128 and 256 bits. It ac- commodates a 128-bit initial value. Any key length is claimed to achieve 128-bit security. The Sosemanuk cipher uses both some basic design principles from the stream cipher SNOW 2.0 and some transformations derived from the block cipher SERPENT. Sosemanuk aims at improv- ing SNOW 2.0 both from the security and from the efficiency points of view. Most notably, it uses a faster IV-setup procedure. It also requires a reduced amount of static data, yielding better performance on several architectures.
1 Introduction
Sosemanuk is proposed as a new synchronous software-oriented stream cipher combining design principles from SNOW 2.0 with transformations derived from SERPENT. It targets improved security properties and software efficiency through a smaller internal state, reduced static data, and an improved key setup procedure.
- Sosemanuk combines basic design principles from SNOW 2.0 with transformations derived from the block cipher SERPENT.
- The cipher supports key lengths from 128 to 256 bits, with every supported length claimed to provide 128-bit security.
- Sosemanuk seeks to avoid structural properties considered potential weaknesses in SNOW 2.0, while retaining resistance to all known attacks for SNOW 2.0 with a 128-bit key.
- A reduced internal state enables more direct mapping onto processor registers, improving efficiency on several architectures.
- Reduced static data lowers data-cache pressure and yields better performance on several architectures.The paper describes the reduced static-data requirement as another efficiency advantage over SNOW 2.0.
- The key setup uses a reduced version of SERPENT to improve classical initialization procedures in efficiency and security.
2 Specification
Sosemanuk combines SERPENT-derived primitives with a ten-word finite-field LFSR. Its specification defines the field representation, LFSR recurrence, initialization primitive, and maximal-period behavior.
- SERPENT and derivatives: SERPENT-derived components include Serpent1, a single S-box layer, and Serpent24, a 24-round initialization primitive.Serpent1 omits SERPENT’s key addition and linear transformation; Serpent24 uses 25 subkeys and encryption only during initialization.
- LFSR and finite-field state: The internal state is primarily a ten-element LFSR over F2^32, with each element represented as a 32-bit value.The register is initialized with ten values and shifted after each recurrence step.
- Underlying finite field: F2^8 is represented using a primitive polynomial, with field addition implemented as bitwise XOR and multiplication by β as a shifted, masked integer operation.The representation uses the basis (β^7, β^6, ..., β, 1).
- Underlying finite field: F2^32 is built as a quotient over F2^8, and multiplication or division by α becomes an 8-bit shift plus a mask-dependent XOR.The same integer-representation approach supports efficient field arithmetic in the LFSR.
2.3 The Finite State Machine
Sosemanuk combines a 64-bit FSM with an LFSR to generate 32-bit outputs, applying Serpent1 to groups of four intermediate FSM values and combining them with LFSR values.
- The FSM stores 64 bits in two 32-bit registers, consumes LFSR words, updates its memory, and produces a 32-bit intermediate output.
- Every four steps, Serpent1 transforms four consecutive FSM outputs, and XOR with four corresponding LFSR values produces the output words.
- Sosemanuk emits 32-bit values, with the first output designated z1 after initialization and grouped encoding recommended in little-endian order.
- At each step, the FSM and LFSR are updated from selected prior state words, while the LFSR value is buffered before shifting.
- Initialization separates key scheduling from IV injection: the key schedule processes the secret key, while IV injection uses the IV and schedule output to initialize internal state.
IV injection
The IV injection uses outputs from rounds 12, 18, and 24 of Serpent24 to initialize Sosemanuk’s internal state.
- The IV is processed by Serpent24, whose outputs after rounds 12, 18, and 24 are selected for initialization.
- Each selected round output consists of four 32-bit words after the linear transformation, except round 24, whose output follows addition of the 25th subkey.
- The selected values are then used to initialize the Sosemanuk internal state.
3 Design rationale
Sosemanuk’s design rationale balances security margins with software efficiency, using separated IV setup, compact state, table-free operations, and nonlinear output processing.
- Key initialization and IV injection: Separating key scheduling from IV injection makes changing the IV cheaper than repeating a complete key setup for a fixed key.
- Key initialization and IV injection: A block cipher underlies IV setup because its security requirements resemble those of a pseudorandom function, while the setup cannot be much faster than a robust block-cipher computation.
- Choice of the block cipher: SERPENT was selected for its analyzed security, lack of static data tables, low cache pressure, and software-oriented round implementation.
- LFSR length: The 10-word LFSR provides a 384-bit internal state, requires 20 unrolled steps, and fits the total state in 12 registers.
- Feedback polynomial: The LFSR feedback polynomial uses sparse taps and coefficients chosen to support efficient arithmetic while avoiding simplified recurrence relations.
- FSM operations: The Trans function combines 32-bit multiplication with bitwise rotation to mix data without static tables, while the mux irregularly decimates FSM inputs to complicate attacks.
- Output transformation: Serpent1 mixes four successive FSM outputs nonlinearly, so each keystream word depends on four intermediate values and attack recovery requires multiple LFSR words.
4 Resistance against known attacks
Sosemanuk is presented as offering 128-bit security under a specified oracle model, while its known-attack analysis reports high complexities and no exploitable linear, correlation, distinguishing, or algebraic weaknesses.
- Security model: Sosemanuk claims 128-bit security against an attacker restricted to 2^128 elementary operations in the stated oracle model.The model includes reset, chosen 128-bit IV initialization, and one-bit stream-output queries.
- Security model: The security claim excludes attackers benefiting from large precomputation because the model does not bound precomputation time.The authors extend the claim to the 128-bit-key variant and larger-key variants under this restriction.
- Time-memory-data tradeoffs: For a 128-bit key and 128-bit IV, the best cited Hellman time-memory-data tradeoff attack requires 2^128 cipher operations.The paper attributes impracticability of these attacks partly to the LFSR length exceeding twice the key length.
- Guess and determine attacks: The authors state that attacks with complexities approximately 2^226 and 2^224 do not compromise Sosemanuk because the design targets 128-bit rather than 256-bit security.The internal state is 384 bits, which the authors identify as unsuitable for a 256-bit-security target.
- Other attacks: The analysis reports that Serpent1 removes linear relations, while the mux operation makes fast correlation attacks impracticable and the algebraic attack intractable.The distinguishing-attack analysis also says the SNOW 2.0 masking attack could not be applied directly because of Serpent1's bitslice design.
5 Implementation
The implementation section supplies an optimized reference C program and detailed test vectors covering key, IV, internal states, intermediate values, and stream output.
- Reference implementation: The optimized reference C implementation can run as a full program and outputs two detailed test vectors.Defining SOSEMANUK_VECTOR supplies the program's own main function.
- Test-vector contents: Each test vector includes the secret key, expanded SERPENT key, 25 Serpent24 subkeys, and the 128-bit IV.The expanded key is represented as a 256-bit little-endian value, while the IV is also shown as four 32-bit words.
- Test-vector contents: Each test vector records the initial LFSR state and initial FSM state before ten repeated rounds of diagnostics.The LFSR state contains s1 through s10, and the FSM state contains R1_0 and R2_0.
- Test-vector contents: For each repeated round, the vectors expose four FSM and LFSR updates, intermediate outputs, Serpent1 input and output, 16 bytes of cipher output, and total stream output.The complete stream output contains 160 bytes.
6 Performance
Sosemanuk is evaluated against SNOW 2.0 and AES-CTR across three architectures, with results emphasizing low static-data requirements and strong software performance on several platforms.
- Evaluation setup: The evaluation compares Sosemanuk, SNOW 2.0, and AES-CTR using reference C implementations on Pentium 4, Athlon64 X2, and Alpha EV6 systems.The tables cover keystream generation, IV setup, and key setup.
- Implementation footprint: The unrolled loop produces a code size between 2 and 5 KB, so the entire code fits in the L1 cache.The range depends on the platform and compiler.
- Implementation footprint: 4 KB of static data is required, three times less than SNOW 2.0, reducing data-cache pressure.This is reported for the reference C implementation.
- Setup costs: Key setup occurs once per key, while each new IV injection uses a small SERPENT-derived block-cipher version.The reported setup performance is therefore tied directly to SERPENT performance.
- Setup costs: The IV-setup and key-setup estimates correspond to about three-quarters of the best published SERPENT encryption and key-schedule performance, respectively.The reference implementation does not reuse the best SERPENT implementation because of intellectual-property considerations.
- Performance results: Sosemanuk remains among the fastest algorithms on several platforms, attributed to effective processor-register mappings and low data-cache pressure.The performance framework includes long-stream, packet, agility, IV-setup, and key-setup measurements.
7 Strengths and advantages of Sosemanuk
Sosemanuk improves SNOW 2.0 through security-oriented mappings and implementation choices. These choices target algebraic, correlation, guess-and-determine, and related weaknesses while improving resynchronization and software efficiency.
- Sosemanuk avoids potential weaknesses through its LFSR design and carefully designed finite-state-machine mappings.
- The Trans function provides low-cost confusion and diffusion while preventing algebraic attacks.
- The mux operation protects against fast correlation and algebraic attacks while remaining efficient to implement.
- The Serpent1 output transformation provides nonlinear equations, good diffusion, and improved resistance to guess-and-determine attacks.
- Separating key setup and IV injection enables faster resynchronization without loss of security.
- Reduced static data and internal state improve register use and reduce data-cache pressure on several platforms, especially RISC architectures.
A Specifications of SERPENT
The appendix recalls the specifications of SERPENT, including its S-box definitions and linear transformation.
- The appendix provides a recall of SERPENT's specifications.
- The recalled specifications include the definitions of the S-boxes.
- The recalled specifications also include the definition of the linear part.
A.1 S-boxes definitions
SERPENT uses eight S-boxes, each acting as a permutation on 4-bit words.
- SERPENT has eight S-boxes.
- Each SERPENT S-box acts on 4-bit words.
- The S-boxes are defined as permutations of Z16.
A.2 Linear part of SERPENT round function
The linear part of a one-round SERPENT function acts on four 32-bit words, with the least significant word designated X0.
- The one-round linear part acts on four 32-bit words.
- The words are ordered as (X3, X2, X1, X0).
- X0 is the least significant word.