Report on Present State of
MULTI-S01 Cipher Evaluation(full evaluation)
January 28, 2002
Takeshi Shimoyama,Yukiyasu Tsunoo,Kiyomichi Araki, Members
Symmetric-Key Cryptography Subcommittee
1

MULTI-S01
z Presented by Hitachi, Ltd. in 2000
z Stream cipher with message authentication

code (MAC)z 256-bit key length, 256-bit initial vector
z Uses PANAMA as pseudo-random number
generator in MULTI-S01

2

Conceptual view of MULTI-S01(encryption)
Encryption key(256-bit)

Initial vector(256-bit)

PANAMA(Pseudo-random number
generation)Plaintext stream(64-bit×N)

Encryption + MAC

Ciphertext streamwith message
authentication code(64-bit×(N+2))

3

Last year’s evaluationz No problems have been discovered so far in termsof the cipher’s security as a stream cipher.
z The cipher has yet to undergo a rigorous
evaluation by an organization such as an academic
society. Thus a follow-up evaluation is necessary.
z In terms of processing speed in the SW, MULTIS01 is among the fastest.
(CRYPTREC Report 2000)
4

Evaluation procedurez The pseudo-random number generator unit

(PANAMA) was evaluated separate from theencryption unit in which modes of operation arerealized.
z Full evaluation details
1. Evaluation in which MULTI-S01 is regarded as modes ofoperation [2]2. PANAMA’s security against theoretical cryptanalysis [2]3. Randomness tests of PANAMA using a computer [1](The numbers in brackets are the number of evaluators foreach evaluation category.)5

1. Evaluation as modes ofoperationz This evaluation pertains to the relationshipbetween security and the method of using
PANAMA (the cipher component) in the MULTIS01 device.
z This evaluation does not go so far as to examine
PANAMA’s internal structure.

6Modes of operation (Evaluator 1)
z The submitter’s definition of security isinsufficient.
z Security was redefined for this evaluation. Basedon the evaluation results, it would seem possible
to reduce from MULTI-S01’s security forencryption and the impossibility of forging
messages to PANAMA’s properties.

7Modes of operation (Evaluator 2)
z The self-evaluation does not provide appropriate

descriptions of the definition of the encryption algorithm
for multiple data streams, and the definition of security as astream cipher with authentication.
z The cipher was evaluated using definitions provided by theevaluator. The evaluation results indicated that MULTIS01’s security for encryption and the impossibility offorging messages could be reduced to PANAMA.
z When MULTI-S01 was compared with “Carter-Wegman
MAC” (a faster cipher with authentication that can berealized by a slight addition of bits to the ciphertext), noadvantages for MULTI-S01 were observed.
82. Theoretical cryptanalysis ofPANAMAz PANAMA has a large factor in the security of MULTI-S01,

so the security of PANAMA itself was evaluated from atheoretical perspective.
z PANAMA is a cipher algorithm proposed by Daemen and
Clapp in 1998. It contains two components: a hashfunction and a pseudo-random number generator.
z Only PANAMA’s pseudo-random number generator
mechanism is used by MULTI-S01. Therefore, only
PANAMA’s pseudo-random number generator mechanism
was evaluated.
9Theoretical analysis (Evaluator 1)z Three different simplifications (PANAMA-S1, -S2, -SM; Evaluator 1 considers PANAMA-SM to
be closest to the real PANAMA) were performed,and the complexity of attack was calculated.
z PANAMA-SM can be cryptanalyzed with anamount of data proportional to 100 and a numberof calculations proportional to 265. (The internal
state of the cipher device can be constructed.)z However, it would be difficult to apply this attack
method to PANAMA itself.
10

Theoretical analysis (Evaluator 2)
z This analysis focused on PANAMA’s initial vector IV(256 bits).
z An analysis of cases where a pseudo-random number
sequence is generated using a different IV selected by anattacker indicated the following:z The same pseudo-random number sequence does notoccur.
z There are no trivial weaknesses in relation todifferential attacks and related-key attacks.
z No weaknesses were discovered in PANAMA, although
the short time period available for the evaluation may havebeen a factor.
11

3. PANAMA randomness testsz PANAMA’s statistical properties were verified using

NIST’s SP800-22.
What is SP800-22?
z SP800-22 is a pseudo-random number statistical testing
tool and document published by NIST.
z The test output consists of 189 different “pass rates”
and “distributions”.
z These tools are used for tests for AES selection.
12

Randomness tests(experimental results)z There do not seem to be any particular

deficiencies in PANAMA’s pseudo-randomness.
* Reference informationz It was learned that the heuristic parameters may
differ from those of genuine random numbers in atleast two locations in the test program included
with NIST’s randomness test document SP800-22(evaluations of “distribution” for test items DFTand Lempel-Ziv).
13

Conclusionz MULTI-S01’s security can be reduced to thesecurity of PANAMA.
z Fatal problems in PANAMA’s security have yet tobe discovered.
z A randomness tests of PANAMA showed noparticular deficiencies.

14