Security Level of Cryptography —Security evaluation (especially in mode part) for the stream cipher
MULTI-S01
December 2001

Contents
1 Summary
1.1 Description of this document . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Principle ﬁndings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
2
2
2

2 Stream Ciphers and their Security
2.1 Syntax of a stream cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Privacy of a stream cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Authenticity of a stream cipher . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
3
4
5

3 Stream-Cipher Cores and their Security
3.1 Syntax of a stream-cipher core . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Perfect privacy of a stream-cipher core . . . . . . . . . . . . . . . . . . . . . . .
3.3 Statistical authenticity of a stream-cipher core . . . . . . . . . . . . . . . . . .

6
6
6
7

4 Deﬁnition of MULTI-S01
4.1 MULTI-S01 as a stream-cipher core . . . . . . . . . . . . . . . . . . . . . . . .
4.2 MULTIS-S01 as a stream cipher . . . . . . . . . . . . . . . . . . . . . . . . . . .

77
95 Security of MULTI-S01-SCC
5.1 Perfect privacy of MULTI-S01-SCC . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Statistical authenticity of MULTI-S01-SCC . . . . . . . . . . . . . . . . . . . .

12
12
12

6 From Stream-Cipher Core to Stream Cipher
6.1 Converting a stream-cipher core to a stream cipher . . . . . . . . . . . . . . . .
6.2 Theorems that justify a focus on stream-cipher cores . . . . . . . . . . . . . . .
6.3 Requisite security property for function P . . . . . . . . . . . . . . . . . . . . .

12
12
13
14

7 Criticisms and Suggestions
7.1 Length restrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 Ciphertext length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3 Forging probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4 Software speed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.5 Generic composition as a better alternative . . . . . . . . . . . . . . . . . . . .

15
15
15
15
16
16

References

18
1

1

Summary

1.1

Description of this document

This document is an evaluation of the MULTI-S01 encryption scheme, as proposed by Hitachi.
The document is based on references [DEF, SELF, SLIDES, EVAL]. It was prepared at therequest of the Information-Technology Promotion Agency, Japan.
This evaluation focuses on the “mode portion” of MULTI-S01. In particular, MULTI-S01
proposes the use of a particular pseudorandom generator, Panama, but the current evaluation does not contain any new cryptanalysis of Panama. Instead, we model the underlying
pseudorandom generator as ideal and proceed from there.

1.2

Background

The object of study. MULTI-S01 is an authenticated-encryption scheme based on a pseudorandom generator (or, more precisely, based on a inﬁnite-output-length pseudorandom function). In order to encrypt a message M having some positive multiple of 64 bits, one ﬁrst uses
the generator to produce a pad of length |M | + 256. The algorithm then speciﬁes how to use
the pad to map the plaintext M into a ciphertext C having |M | + 128 bits. The sender would
then transmit C to the receiver. The receiver recomputes the same pad κ and then uses it torecover from C the ciphertext M . During message recovery, the receiver may obtain a signal
invalid instead of recovering a message M in the message space. Typically, the connection
would be dropped in this case. The intent is that any adversarial modiﬁcation to the ciphertext
should result in the receiver recovering invalid.
Authenticated-encryption methods that correctly intertwine privacy and authenticity ina single, integrated mode only recently emerged, with the work of [IAPM]. The customaryalternative—providing for privacy and authenticity by separate primitives and the “gluing them
together”—has been called the generic composition paradigm, and it is analyzed in [BeNa].
The main motivation for more tightly comingling privacy and authenticity is a potential savingsin speed.
The methods of [IAPM], as well as later work like [OCB], build an authenticated-encryption
scheme from a block cipher, not a pseudorandom generator. Motivated by the fact that stateof-the-art pseudorandom generators are faster per byte of output than state-of-the-art blockciphers, the authors of MULTI-S01 set forth to devise an authenticated-encryption scheme
built on top of a pseudorandom generator. A good idea, even if the authors did not quite pull
it oﬀ.

1.3

Principle ﬁndings

We summarize our main results and ﬁndings:
1. Document [DEF] only looks at how to encrypt a single message M . It is not very clear
about how to encrypt a sequence of plaintexts. This was a major hole in the exposition.
2. We needed to ﬁll this hole before we could proceed with any meaningful analysis. Thus
the exposition of MULTI-S01 we give here goes beyond that in [DEF] to fully specify what2

we guess to be the intended way to use MULTI-S01 to encrypt a sequence of messages.
Our exposition includes a formal treatment of stream ciphers and stream-cipher cores.
3. There is no formal treatment in the submission (or, more broadly, in the cryptographic
literature) for the security of a stream-cipher authenticated-encryption scheme. We remedy this, developing formal deﬁnitions for authenticity appropriate to the stream-cipher
setting. This was essential before we could decide if MULTI-S01 was “right.”
4. The formal treatment allows one to reach the (initially non-obvious) conclusion that,assuming privacy, an inability to forge after querying a single message implies an inability
to forge after asking a sequence of messages. This result justiﬁes limiting attention towhat ﬁrst looks to be a weak kind of attack described in [SELF].
5. We found the main criticisms of [EVAL] to be without signﬁcant merit. That evaluation
complained of a lack of “robustness” because one must use distinct keys for distinct
messages. This is an intrinsic aspect of stream ciphers (when using an exposition similar
to that of used in [DEF]) and not a relevant criticism to MULTI-S01. Secondly, [EVAL]
discounted the claims of integrity, perhaps not understanding them, pointing out theobvious and irrelevant facts that one can forge messages if one knows the key, and that
there is some nonzero probability of forgery. In fact, the claims of integrity made in[SELF] are valid and are especially meaningful in light of the results we give here.
6. Despite disagreeing with the thrust of [EVAL], we too did not ﬁnd major merit in
MULTI-S01. The reason is that there are alternative methods, using Carter-Wegman
MACs, which are faster, architecturally cleaner, increase ciphertext length by fewer bits,
and apply to messages of any bit length.
Finally, we mention that, like all stream ciphers, the eﬀective use of MULTI-S01 requires
the receiver to maintain state and that the sender and receiver communicate over a reliablechannel. These are serious restrictions and limit the utility of a stream cipher that does notbring with it major compensating advantages. We did not ﬁnd such compensating advantages
in MULTI-S01 and, therefore, would not recommend it for standardization.

2

Stream Ciphers and their Security

It is the stated goal of MULTI-S01 to achieve both privacy and authenticity, but there is noformal deﬁnition of either goal in any of [DEF, SELF, EVAL]. More broadly, there are nodeﬁnitions in the literature for the security of a stream-cipher based authenticated-encryption
scheme. We remedy this, giving a model and deﬁnitions for the desired goals.
Notions of security for authenticated encryption only recently emerged, and are best described in [BeNa]. However, the stream-cipher setting is diﬀerent from the setting consideredin [BeNa] and related works, necessitating new deﬁnitions.

2.1

Syntax of a stream cipher

We begin by describing “syntax” for stream ciphers, divorced from any notion of security.
Formally, a stream-cipher is a triple of algorithms SC = (Key, Enc, Dec) as follows:3• The key-generator Key is a set endowed with a distribution.
• Encryption algorithm Enc : Key × Par × Msg → {0, 1}∗ is a stateful, deterministic algorithm. It takes a key K ∈ Key, a parameter Q ∈ Par, and a message M ∈ Msg. It returns
a ciphertext C ∈ {0, 1}∗ of length |M | + r. Here r > 0 is a number (how much longer aciphertext is than a plaintext) and Msg is a linear-time testable set (the message space).
• Decryption algorithm Dec : Key × Par × {0, 1}∗ → {0, 1}∗ is a stateful, deterministic
algorithm. It takes a key K ∈ Key, a parameter Q ∈ Par, and a ciphertext C ∈ {0, 1}∗ .
It returns either a plaintext M ∈ Msg of length |C| − r or else the distinguished symbol
invalid.
One requires that if K ∈ Key and Q ∈ Par and a sequence of messages M 1 , · · · , M m ∈ Msg gets
1mencrypted, in order, using EncQ
K , resulting in ciphertexts C , · · · , C , then decrypting theseQ1m
ciphertexts, in order, using DecK , results in plaintexts M , · · · , M .
We say that a ciphertext C is invalid (with respect to a given key K and parameter Q) if
Q(C) = invalid; otherwise, C is valid.
DK
Discussion. The parameter Q is non-standard for stream ciphers, but it is used in MULTI-S01
and must be directly reﬂected in the deﬁnitions. Think of each Q ∈ Par as determining aseparate stream with which one can encrypt communications. All of these streams are logicallyseparated. Sender and receiver must “know” Q, but it need not be secret. As a typical example,
one might set Q to some ﬁrst value, Q1 , and then, if some message should get dropped, thereceiver could request a “re-synch” and the sender would respond by choosing a new Q-value
Q2 and carrying on, transmitting the new Q-value with the next message.
Making ciphertexts longer than plaintexts by a ﬁxed constants is certainly not necessary,
but it shall be convenient later on.
We emphasize that both Enc and Dec are stateful. This is a fundamental characteristic of
stream ciphers.

2.2

Privacy of a stream cipher

We give a very strong deﬁnition of privacy: indistinguishability from random bits (under anadaptive chosen-message attack). The notion is used, for example, in [OCB].
Fix a stream cipher SC = (Key, Enc, Dec) with parameters r, R. Consider an adversary A
with one of two types of oracles:• A real encryption oracle EncSC begins by picking a random value K ∈ Key. Then, on
input of (M, Q), it returns EncQ
K (M ).
• A random oracle RanSC has the following behavior: on input (M, Q), it returns a stringof |M | + r random bits.
An adversary A is valid if every query (M, Q) it asks falls in Msg × Par. We only consider
valid adversaries. (Alternatively, have all oracles respond to invalid queries by returning theemptystring.) We let
EncSC= 1] − Pr[ARanSC = 1]
AdvPRIVSC (A) = Pr[A4

be the adversary’s “advantage” in distinguishing which of the two types of oracles that is has.
This is our measure of privacy.
Informally, a scheme is private if the encryptions of plaintexts look like the expected numberof random bits. The notion may be stronger than “necessary,” but it is achievable and has
desirable characteristics.
A stream cipher SC is perfectly private if, for any adversary A, AdvPRIVSC (A) = 0.

2.3

Authenticity of a stream cipher

Definition. Fix a stream-cipher SC = (Key, Enc, Dec). Suppose we run an adversary with two
oracles: an encryption oracle Enc as described already, and a (stateful) decryption oracle Dec.
The decryption oracle has the following behavior. It is initialized with the same string K ∈ Key
that initializes the encryption oracle. Then, on input (C, Q), it returns M = DecQ
K (C). Notethat M may be invalid.
Given a stream cipher SC = (Key, Enc, Dec) and an adversary A, run A with encryption
oracle Enc and decryption oracle Dec. If A ever asks a decryption query that results ininvalid being returned, then A fails: it does not forge. Otherwise—all responses to Dec
are valid—focus on the Enc and Dec queries that use some one particular Q-value. Thenthe adversary asks Enc some sequence of messages M 1 , M 2 , · · ·, getting responses C 1 , C 2 , · · ·.
Interleaved with these queries, the adversary asks it decryption oracle Dec some sequence of
ciphertexts C̃ 1 , C̃ 2 , · · ·, getting back plaintexts M̃ 1 , M̃ 2 , · · ·. We say that the adversary forges(during this run) if some C̃ s is valid (that is, M̃ s ∈ Msg) but C̃ 1 , C̃ 2 , · · · , C̃ s is not a preﬁx of(A) denote the probability that adversary A forges. Let AdvAUTH(m)
C 1 , C 2 , · · ·. Let AdvAUTH
SC
SC
AUTH
denote the maximal value of AdvSC (A) over all adversaries A that make Enc queries (M, Q)
where |M | ≤ m and Dec queries (C, Q) where |C| ≤ m − r.
Discussion. The authenticity notion can be understood as follows. Imagine a sender andreceiver speaking over a channel. An adversary attacking a stream cipher and able to mounta chosen-plaintext attack can ask the sender to encrypt M 1 , · · · , M q , giving rise to ciphertexts
C 1 , · · · , C q that the adversary sees. The adversary knows that if it sends to the receiver
C 1 , C 2 , . . . , C q this will give rise to the recovery of valid messages (namely, M 1 , · · · , M q ). Any
preﬁx of M 1 , . . . , M q will also give rise to a sequence of valid messages. So we say that theadversary A wins if it can get anything else to be deemed valid.
For example, if the adversary gets a sequence of ciphertexts C 1 , C 2 , C 3 , C 4 for plaintexts
M 1 , M 2 , M 3 , M 4 and, using this data, the adversary concocts C̃ 3 where C̃ 3 = C 3 and yet thesequence of ciphertexts C 1 , C 2 , C̃ 3 are all valid, then the adversary has forged. Note that Dec
is stateful and so, for example, the third message in the sequence C 1 , C 2 , C 2 should certainly
not be regarded as valid.
While we had the decryption oracle return the actual plaintext, it makes for an equivalentdeﬁnition for the oracle to return only an indication of valid/invalid. This is because theadversary wins (forges) as soon as it obtains a nontrivial and valid decryption-oracle response.
The value of that response is never used.
We have decided to give the adversary no credit—it does not forge—if the decryption oracle
returns invalid. This is meant to capture the expectation that a connection is dropped after
an authentication failure. Alternatively, we could allow the adversary to play on, and possiblyforge.
5

3

Stream-Cipher Cores and their Security

A stream-cipher core is a lower-level object than a stream cipher. From a stream-cipher core
one can build a stream cipher in a standard way, and yet a stream-cipher core is a conceptuallydiﬀerent and simpler object. A stream-cipher core lets you encrypt just one message, using a
key of the appropriate length for that message. There is no state and no parameter Q for a
stream-cipher core, and the security deﬁnitions are simpler. And here we shall only consider
information-theoretic security deﬁnitions for stream-cipher cores.
In this section we describe the syntax for a stream-cipher core and then we give notions ofprivacy and authenticity for these objects.

3.1

Syntax of a stream-cipher core

A stream-cipher core is a triple of algorithms SCC = (K, E, D) as follows:• The key-generator K is a probabilistic algorithm K : N → {0, 1}∗ . It takes a number
m > 0 (the length of the plaintext that needs to be encrypted) and (depending on internalcoin tosses) it returns a string K ∈ {0, 1}∗ having length m + R, for some constant R.
• Encryption algorithm E is a deterministic function that takes a message M ∈ Msg and a
key K of length |M | + R and returns a string C = EK (K) of length |M | + r. Here r > 0 is
a number (how much longer a ciphertext is than a plaintext) and Msg is a a linear-time
testable set (the message space).
• Decryption algorithm D takes a ciphertext C ∈ {0, 1}∗ and a string K of length |C|+R−r
and returns a value M = DK (M ) which is either a string in Msg of length |C| − r or elseis the distinguished symbol invalid.
We require that for any m, K ∈ K(m), and M ∈ Msg, if C = EK (M ) then DK (C) = M .
We say that C is invalid (with respect to a given key K) if DK (C) = invalid; otherwise,
C is valid.
Obtaining keys from infinite strings. We assume that the distribution K(m) can beobtained as follows: choose an inﬁnite random string κ and process bits of κ left-to-right until
one obtains an adequate number of bits—say nbits(κ, m) bits. Then output a function of those
bits as the key K = extract(κ, m) ∈ {0, 1}m+R . Functions nbits and extract are associated tothe stream-cipher core SCC.
By the assumption of the last paragraph we may use κ ∈ {0, 1}ω to name a key for E or D:
that is, Eκ (M ) or Dκ (C) instead of EK (M ) or DK (C).
Discussion. The restrictions that ciphertexts are a ﬁxed amount longer than plaintexts, r
bits, and that keys are a ﬁxed amount longer than plaintexts, R bits, are unnecessary but
simplify our later deﬁnitions.

3.2

Perfect privacy of a stream-cipher core

A stream-cipher core SCC = (K, E, D) with parameters r, R and message space Msg is saidR
to be perfectly private if, for every M ∈ Msg, the distribution [K ← K(|M |) : EK (M )] is theuniform distribution on |M | + r bits.
6

3.3

Statistical authenticity of a stream-cipher core

We give a strong notion of authenticity for a stream-cipher core SCC = (K, E, D) with parameters r, R and message space Msg:
AdvauthSCC (m) =max {Pr[Dκ (C̃) = invalid | Eκ (M ) = C}

M,C,C̃

κThe maximum is over all M, C, C̃ such that C = C̃ and |M | ≤ m and |C| ≤ m + r and theconditioning event above is nonempty.
Explanation. The deﬁnition above can be understood as follows. An adversary asks forthe ciphertext C of a single message M having at most m bits. Based on this, it tries toconcoct a forgery C̃ for some (possibly unknown) message M̃ that has at most m bits. The
forgery is with respect to the same underlying key that encrypted M . The value Advauth
SCC (m)upperbounds the probability that the adversary will succeed in this game. It is a pessimistic
upperbound, insofar as we ﬁx an (M, C) that is most advantageous for the adversary.

4

Deﬁnition of MULTI-S01

We will take two diﬀerent views about what MULTI-S01 is: a stream-cipher core and a stream
cipher. Only the former object is clearly speciﬁed in [DEF], but perhaps the latter may beviewed as implicit.
The description of MULTI-S01 given here does not closely follow that in [DEF]. In particular, we have had to introduce our own abstraction boundaries, both as a way to clarify what
is going on in MULTI-S01 and also as a way to facilitate a more scientiﬁc exposition of the
security properties of MULTI-S01.

4.1

MULTI-S01 as a stream-cipher core

We ﬁrst describe MULTI-S01 as a stream-cipher core MULTI-S01-SCC = (K, E, D). Thus K
shall be a probabilistic function and E and D shall be deterministic ones. One samples from
K(m) to determine a key K to be used to encrypt a message M of length m. To encrypt
another message, sample to determine another key.
Illustration. We begin with a picture. Encryption under MULTI-S01 is depicted in Figure 1.
Referring to that picture, a message M which is a positive multiple of 64 bits is broken into
64-bit pieces M1 · · · Mm . A keystream A B1 · · · Bm S is then used to encrypt M , where each A,
Bi , and S is 64 bits. The value R is a ﬁxed constant, say R = 064 . Two primitives are employed:
xor of 64-bit values (denoted ⊕) and GF(264 )-multiplication of 64-bit values (denoted ⊗). The
resulting ciphertext C = C1 · · · Cm+2 is transmitted to the receiver. The receiver recovers
M in the natural way, but rejects M if the recovered values S  or R are diﬀerent from theanticipated values S and R.
Key generation. The function K takes a number m (the message length for the message wewill subsequently encrypt) and outputs a key K. For MULTI-S01, the key K output by K(m)consists of 64 random-but-nonzero bits followed by m + 192 random bits.

7

M4

S

R

=

=

=

=

=

P2

P3

P4

P5

P6

M2

=

M3

M1
P1

B1

B2
F2

F1
A

B3

A

C1

B4
F3

F4

A

C2

A

C3

B6

B5
F5
A

C4

A

C5

C6

Figure 1: The encryption function at the core of MULTI-S01. All blocks are 64 bits. We are
encrypting the 4-block message M = M1 M2 M3 M4 into ciphertext C = C1 C2 C3 C4 C5 C6 withkey K = A B1 B2 B3 B4 B5 B6 S and “redundancy” R.
function K(m)begin
RA ← {0, 1}64 \ {064 }R
B ← {0, 1}m+128
R
S ← {0, 1}64
K←ABS
return K
end

Encrpytion. First, ﬁx a constant R ∈ {0, 1}64 (the “redundancy”). The constant R is used
for both encryption and decryption. Let M ∈ ({0, 1}64 )+ be the message we wish to encrypt.
That is, M is a positive multiple of the blocksize, which is 64 bits. Document [DEF] assumes
that |M | ≤ 238 (ie., M has at most 232 blocks). So, overall, the message space for MULTI-S01
32
is Msg = {{0, 1}64 , {0, 1}2·64 , . . . , {0, 1}2 ·64 }. Let K be a key determined by running K(|M |).
That is, the key K used to encrypt M is four blocks longer than M , but the ﬁrst block isnonzero. We now deﬁne EK (M ) as follows:8

function EK (M )begin
Parse M into 64-bit blocks M1 · · · Mm
Parse K into 64-bit blocks A B1 · · · Bm Bm+1 Bm+2 S
Let Mm+1 ← S
Let Mm+2 ← R
Let F0 ← 064
for i ← 1 to m + 2 do
Fi ← Mi ⊕ Bi
Ci ← A ⊗ Fi ⊕ Fi−1
odreturn C ← C1 · · · Cm Cm+1 Cm+2
end
Above, ⊕ is used to denote xor of 64-bit strings, while ⊗ is used to denote multiplicationof points in the ﬁnite ﬁeld GF(264 ) using a standard representation of ﬁeld points as 64-bit
strings, as speciﬁed in [DEF]. As usual, the multiplication operator is given higher precedence
than the addition operator: A ⊕ B ⊗ C means A ⊕ (B ⊗ C).
Decryption. The decryption function for MULTI-S01 is deﬁned as follows.
function DK (C)begin
If |C| is not divisible by 64 then return invalid
Let c ← |C|/64
If c ≤ 2 or c > 232 then return invalid
Let m ← c − 2
Parse C into 64-bit blocks C1 · · · Cm Cm+1 Cm+2
Parse K into 64-bit blocks A B1 · · · Bm Bm+1 Bm+2 S
Let F0 ← 064
for i ← 1 to m + 2 do
Fi ← A ⊗ (Ci ⊕ Fi−1 )Mi ← Fi ⊕ Biod
If Mm+1 = S or Mm+2 = R then return invalid
return M ← M1 · · · Cm
end
Note that decryption may return the distinguished symbols invalid to indicate that the ciphertext received should be regarded as inauthentic.

4.2

MULTIS-S01 as a stream cipher

One deﬁciency of document [DEF] is its lack of clarity about how protocol MULTI-S01-SCC =(K, E, D) should be used to encrypt a sequence of messages M 1 , M 2 , M 3 , · · ·. The document9

describes how to construct from an underlying, ﬁxed-length key K (say 256 bits) a keystream
K of the appropriate type and length to encrypt a single message M , but it goes no further. We
describe that method and then extend it to solve the “real” problem at hand—the constructionof a stream cipher from the MULTI-S01 stream-cipher core.
Note that in this subsection we shall be simultaneously handling two issues: how to use aﬁxed length key K (say 256 bits) instead of a key K that depends on the message length; andhow to encrpyt a sequence of plaintexts, not just one.
Description of single-message mode. The MULTI-S01 speciﬁcation [DEF] addresses theencryption and decryption of a single message, M , this message having a nonzero multiple of
64 bits, using a ﬁxed-length key K. The method works as follows. The sender and receiverare assumed to share a key K drawn from some set Key. They also share a “deviation parameter” Q, drawn from some set Par. Using a function P : Key × Par → {0, 1}ω , the senderand receiver map K and Q to a (|M | + 256)-bit keystream K = PK (Q). The ciphertext thesender computes and transmits to the receiver is C = EK (M ). The encryption and decryption
methods are now as follows:
function EncQ
K (M )
beginκ ← PK (Q) (κ an inﬁnite string)i←1while κ[i..i + 63] = 064 do i ← i + 64
K ← κ [i..|M | + 255]
return EK (M )endfunction DecQ
K (M )
beginκ ← PK (Q)i←1while κ[i..i + 63] = 064 do i ← i + 64
K ← κ [i..|M | + 255]
return DK (M )end

The stream cipher is MULTI-S01-SC = (Key, Enc, Dec). This should not be confused with thestream-cipher core MULTI-S01-SCC = (K, E, D). The former uses a “short” key K while thelatter uses a “long” key K.
In single-message mode, the deviation parameter Q should be used for at most one message:
with every message one must choose a new deviation parameter Q. This will be relaxed shortly.
Panama, and what IS Panama. The deﬁnition of MULTI-S01 [DEF] suggests that P
be the function Panama described in [PANA]. The inventors refer to this function as a
pseudorandom generator. We comment that the name pseudorandom generator is not quite
correct—neither for what Panama is nor for the object that MULTI-S01 requires. Namely, apseudrandom generator is an algorithm P : Key → {0, 1}ω but MULTI-S01 needs an algorithm
P : Key × Par → {0, 1}ω . (Here {0, 1}ω means an “inﬁnite” sequence of random bits. In
actuality, one is only using some ﬁnite preﬁx of this inﬁnite string.) Such a map is more properly
called an inﬁnite-output-length pseudorandom function. Panama is an inﬁnite-output-length
pseudorandom function. It has a signature Panama : {0, 1}256 × {0, 1}256 → {0, 1}ω , meaningthat the key length and the deviation-parameter length are each 256 bits. Therefore, using
Panama as above, MULTI-S01 allows one to encrypt a message M (having a positive multipleof 64 bits) using a 256-bit key K and a 256-bit deviation parameter Q into a ciphertext
C = EncQ
K (M ).
10

Stream-per-message mode. The deﬁnition of MULTI-S01 given in [DEF] is not speciﬁc
about how one should encrypt a sequence of messages M 1 , M 2 , · · ·. One possiblity is what
we call stream-per-message mode: for each message M i the sender chooses a new deviationiiparameter Qi and then transmit C i = EncQ
K (M ) along with adequate information for theireceiver to recover Q . As an exmple, one could encrypt the i-th message as i and C i =EnciK (M i ), where i, as a superscript to E, indicates the string in Par encoding the number iin the usual way (recall Q = {0, 1}256 when using Panama). If the sender and receiver arecommunicating over a reliable channel then i would not need to be explicitly transmitted,
since the receiver can maintain the matching value himself. If the sender and receiver arecommunicating over an unreliable channel then i could be transmitted in the clear, as one
does not need for Qi to be secret. It is essential that the values Q1 , Q2 , Q3 , · · · used for
M 1 , M 2 , M 3 , · · · are all distinct.
Multi-message mode: constructing a proper stream cipher. We expect that theinventors of MULTI-S01 didn’t really envision the use of stream-per-message mode. Besides
the ineﬃciency associated to re-keying the pseudorandom function, stream-per-message mode
goes against the basic idea of how stream ciphers are supposed to be used. That idea entails
that the sender and receiver share an eﬀectively inﬁnite string κ and use its pieces for eachof the diﬀerent messages that get sent. Namely, the sender wants to transmit some sequenceof messages M 1 , M 2 , · · ·. To accomplish this, the sender will partition the string κ into pieces
K 1 , K 2 , · · ·, as needed, and the sender will use K i to encrypt M i into ciphertext C i .
The fact that MULTI-S01 chose to use a pseudorandom function instead of a pseudorandom
generator suggests that the inventors have in mind still more ﬂexibility: allowing the sender to“re-synch” at will—choose a new value Q and then transmit a message sequence M 1 , M 2 , · · ·using the keystream κ determined by K and Q. The mode, which we call multi-message mode,
is MULTI-S01-SC = (Key, Enc, Dec), deﬁned as follows:
function EncQ
K (M )
begin
static in(Q) ← 1 for all Q ∈ Par
κ ← PK (Q)while κ[in(Q)..in(Q) + 63] = 064
do in(Q) ← in(Q) + 64
K ← κ [in(Q)..|M | + 255]
in(Q) ← in(Q) + |M | + 256
return EK (M )endfunction DecQ
K (M )
begin
static in(Q) ← 1 for all Q ∈ Par
κ ← PK (Q)while κ[in(Q)..in(Q) + 63] = 064
do in(Q) ← in(Q) + 64
K ← κ [in(Q)..|M | + 255]
in(Q) ← in(Q) + |M | + 256
return DK (M )endNote that our treatment of multi-message mode is a proper extension of single-message mode:
the two modes agree when presented a sequence of distinct Qi -values.
At this point we have a stream-cipher core, MULTI-S01-SCC, and a stream cipher proper,
MULTI-S01-SC.

11

5

Security of MULTI-S01-SCC

Though the language of [EVAL] is quite diﬀerent from that introduced here, [EVAL] does, ineﬀect, give valid proofs for the privacy and authenticity of MULTI-S01-SCC. We now state
the requisite theorems, as adapted from [EVAL].

5.1

Perfect privacy of MULTI-S01-SCC

For the MULTI-S01 stream-cipher core, privacy is perfect. This is quite natural. Referring
to Figure 1, note that B6 is uniformly distributed and A is non-zero so A ⊗ B6 is uniformly
distributed. This value is independent of the value A ⊗ P6 ⊕ F5 it gets xor’ed with to form C6 ,and so C6 is uniformly distributed. The same reasoning now applies to C5 , C4 , · · · , C1 , and we
can conclude the following.
Theorem 1 MULTI-S01-SCC is perfectly private.

5.2

Statistical authenticity of MULTI-S01-SCC

Possibly the most interesting part of [SELF] was an argument along the following lines. Supposethat an adversary sees a MULTI-S01-SCC ciphertext C for a plaintext M produced under arandom key K = ABS. Information theoretically, the ciphertext tells the adversary nothing
about A. In the absence of any information about A (even with complete information aboutB, S), a candidate ciphertext C̃ diﬀerent from C will be valid with a probablity easily boundedusing some case analysis and the fundamental theorem of algebra. In our language, the result
from [SELF] is as follows.
64
Theorem 2 Advauth
MULTI-S01-SCC (m) ≤ (m/64 + 2)/(2 − 1).

(The division by 64 is simply to convert to blocks, the addition of 2 accounts for the lengtheningof the ciphertext, and the subtraction by 1 is because A = 064 .) Though we found the expositionof this result in [SELF] somewhat lacking, the result and proof approach are correct, so we do
not repeat that work here.

6

From Stream-Cipher Core to Stream Cipher

As we have just explained, [SELF] contains what amounts to a proof of perfect privacy andstatistical authenticity for the MULTI-S01-SCC stream-cipher core. At ﬁrst glance, this falls
well short of proving what is actually desired: proving that the stream cipher MULTI-S01-SC
achieves privacy and authenticity. We now argue that this is not problem: under our deﬁnitions,the manner in which MULTI-S01-SCC is promoted from a stream-cipher core to a stream cipher
automatically promotes privacy and authenticity, too.

6.1

Converting a stream-cipher core to a stream cipher

Let SCC = (K, E, D) be a stream-cipher core with parameters r, R and associated functions
nbits(·, ·) and extract(·, ·). Let P : Key × Par → {0, 1}ω be a function. Consider the following
way to extend stream-cipher core SCC = (K, E, D) to a stream cipher SC = (Key, Enc, Dec):
12

function EncQ
K (M )
begin
static in(Q) ← 1 for all Q ∈ Par
κ ← PK (Q)m ← |M |K ← extract(κ[in(Q)..], m)in(Q) ← in(Q) + nbits(κ[in(Q)..], m)
return EK (M )endfunction DecQ
K (M )
begin
static in(Q) ← 1 for all Q ∈ Par
κ ← PK (Q)m ← |M |K ← extract(κ[in(Q)..], m)in(Q) ← in(Q) + nbits(κ[in(Q)..], m)
return DK (M )end

The above extension agrees with how we have extended MULTI-S01 from a stream-cipher core
to a stream cipher. In particular, our earlier exposition coincides with the above where extractand nbits are deﬁned byfunction nbits(κ, m)
begin
i←0
while κ[i + 1..i + 64] = 064 do i ← i + 64
return i + m + 256
endfunction extract(κ, m)
begin
i←0
while κ[i + 1..i + 64] = 064 do i ← i + 64
return κ[i + 1..m + 256]
end

The information-theoretic extension of a stream-cipher core. One can think of
the function P : Key × Q → {0, 1}ω in a couple of ways: as a typical pseudorandom function,such as Panama, where Key = {0, 1}κ is a ﬁnite set; or as the function P(K, Q) = K(Q),where Key is a map from Par to {0, 1}ω . The latter gives an information-theoretic extensionof a stream-cipher core to a stream cipher; the former, a complexity-theoretic one.

6.2

Theorems that justify a focus on stream-cipher cores

The following results eﬀectively justify the security treamement of [SELF]. In that work,
the authors argue that MULTI-S01-SCC achieves perfect privacy and that MULTI-S01-SCC
achieves the expected degredation in authenticity. By looking at security only with respect
to the stream-cipher core, the analysis eﬀectively pays attention only to what happens if
one encrpyts a single message and tries to forge a single ciphertext after having seen a single
plaintext/ciphertext pair. It turns out that this is enough. Our ﬁrst theorem speaks to privacy.

13

Theorem 3 Let SCC = (K, E, D) be a stream-cipher core and let SC = (Key, Enc, Dec) be
its information-theoretic extension. Suppose SCC is perfectly private. Then SC is perfectly
private, too.
Theorem 3 seems reasonably obvious and so we omit its proof.
Our next theorem speaks to the authenticity of the information-theoretic extension of a
stream-cipher core. Note that privacy is necessary for this second result.
Theorem 4 Let SCC = (K, E, D) be a stream-cipher core and let SC = (Key, Enc, Dec) be
its information-theoretic extension. Assume that SCC is perfectly private. Then, for any m,
AdvAUTH(m) ≤ AdvauthSC
SCC (m).
Proof sketch. Let A be an adversary that attacks the stream cipher SC = (Key, Enc, Dec)
obtained from stream-cipher core SCC = (K, E, D). Without loss of generality (by the standard
averaging argument), assume that A is deterministic. We construct a tuple (M, C, C̃) where|M | ≤ m, |C| = |M | + r, |C̃| ≤ m + r, and such that Prκ [Dκ (C̃) = invalid | Eκ (M ) = C] ≥(A).
AdvAUTHSC
To construct (M, C, C̃), start oﬀ by running adversary A. This adversary has two oracles:
EncSC and DecSC . When A makes a query (M, Q) to its EncSC oracle, answer with |M | + r
random bits, and record the query and its answer. Let (M 1,Q , . . . , M a(Q),Q ) record the sequenceof queries asked by A using parameter Q, and let (C 1,Q , . . . , C a(Q),Q ) record the corresponding
answers. When A makes a query (C, Q) to its DecSC oracle, let (C̃ 1,Q , . . . , C b(Q),Q ) record thesequence of queries, to date, having parameter Q. Then if (C̃ 1,Q , . . . , C b(Q),Q ) is a preﬁx to(C 1,Q , . . . , C a(Q),Q ), return C a(Q),Q . Otherwise, consider (M, C, C̃) to be a “candidate triple.”
Note that we have simulated the “correct” behavior for EncSC because of the perfectprivacy of SC.
By our deﬁnitions of stream-cipher authenticity, if C̃ is not a valid forgery then the adversray A has not and will never forge on this run. On the other hand, if C̃ is a valid forgery thenthe adversary A has succeeded on this run.
(A) can be
When A forges it produces a candidate triple (M, C, C̃). The value AdvAUTH
SC
regarded as a a weighted sum λM,C,C̃ Pr[A forges | candidate triple (M, C, C̃)]. Thus there(A).
is a tuple (M, C, C̃) such that Pr[A forges | candidate triple (M, C, C̃)] ≥ AdvAUTH
SC

6.3

Requisite security property for function P

None of [DEF, SELF, EVAL] discuss the properties that P needs to have in order for MULTI-S01
to be secure. But a necessary and suﬃcient property for P is that it be secure in the usual
sense of a pseudorandom function. We now review that notion.
Let P : Key × Par → {0, 1}ω . Consider an adversary A having one of two oracles: a “real”
oracle or a “random” oracle. A real oracle behaves as follows. It begins by choosing a randomR
key K ← Key. Then, to any query (X, ), the oracle returns the ﬁrst  bits of PK (X). A
random oracle behaves as follows. It begins by associating to every string X an inﬁnite stringof random bits ρ(X). Then, to any query (X, ), the oracle returns the ﬁrst  bits of ρ(X).
The advantage that A gets in attacking the pseudorandom function P is the real number
Real
Advprf= 1] − Pr[ARand = 1]
P (A) = Pr[A14where the oracles “Real” and “Random” act in the way we have just described. Informally, a“good” pseudorandom function is a map P for which Advprf
P (A) is small (close to 0) whenever A
is computationally reasonable algorithm (it runs in a reasonable amount of time and obtains
from its oracle a reasonable number of bits).

7

Criticisms and Suggestions

Much of this report has focussed on verifying that, fundamentally, MULTI-S01 is correct:
properly used, MULTI-S01 does provide privacy and authenticity, with the expected bounds,
assuming Panama (say) is secure in the sense of an inﬁnite-output-length pseudorandomfunction. Thus we ﬁnd no basis for the main criticisms of [EVAL] that vaguely questioned
the privacy and authenticity of MULTI-S01. All the same, we are not very supportive of the
MULTI-S01 technique. Let us explain the reasons.

7.1

Length restrictions

MULTI-S01 requires that messages to be encrypted have a length which is a positive multipleof 64 bits. While mandatory padding techniques can of course be used to ensure this, a modern
and reﬁned encryption algorithm can and should do better, saving on communication bits. One
would prefer a solution for which ciphertext lengths will not be increased unnecessarily, and it
is not hard to construct such techniques. Generic composition of a Vernam cipher and a MAC
is one such a technique.

7.2

Ciphertext length

The length of a MULTI-S01 ciphertext C for a plaintext M is |C| = |M | + 128. (If mandatory
padding is added so as to address the issue of the last subsection, the length of a ciphertext
for a plaintext M becomes longer still.) This would be ﬁne if the forgery probability were approximately M  · 2−128 , say. (Here M  means |M |/64.) But it is not; the forgery probability
is approximately M  · 2−64 . For such a forgery probability one should not be spending 128
extra bits, but no more than 64. Indeed we do not understand why the inventors choose to
expend two blocks in order to get authenticity in MULTI-S01 when it would seem to be simple
to make do with one.

7.3

Forging probability

The forging probability of approximately M  · 2−64 may be larger than is acceptable for some
applications. We would suggest that a new authenticated-encryption scheme should be able totransmit a message in a way so as to have forging probability more like M  · 2−128 . Ideally,
one should be able to truncate a 128-bit tag so that if τ bits are transmitted then one gets a
forging probability of approximately 2−τ . Even if the tag were extended to 128 bits, results
like this may not be true with the method of MULTI-S01 as the security impact of truncationon the tag is far from clear.

15

7.4

Software speed

The main motivation for integrating privacy and authenticity is to obtain speed beneﬁts
unobtainable (or diﬃcult to obtain) through generic composition. But data presented in[SELF, SLIDES], as well as back-of-envelope calculations, suggest that MULTI-S01/Panama
does not obtain speeds superior to those obtainable by generic composition. Consider thePentium III speeds reported in [SLIDES] (which appear to be the fastest ﬁgures reported):
17.6 cycles/byte for 256 KByte messages. This is inferior with speeds reported by Lipmaa for
OCB-AES128 encryption: 16.9 cycles/byte for 1 KByte messages.
The authors of [SELF] suggest that performance suﬀers on a 32-bit processor like a Pentium III because of the lack of available 64-bit instructions (discounting MMX instruction).
But the inventors’ ﬁgures for a 64-bit platform are not particularly better: [SLIDES] reports
17.7 cycles/byte for a 4 KByte message.
Key setup is quite slow for MULTI-S01/Panama; the authors of [SELF] report key setup
times of about 32,000 cycles. Compared to AES key-setup, this is enormous, and it largely
limits MULTI-S01 applicability to contexts in which a long-lived session is being initiated.
In view of the added diﬃculty of using a stream cipher compared to an authenticatedencryption scheme based on a block cipher, we feel that the target speed for a streamcipher-based authenticated-encryption scheme needs to be a substantial amount faster than
the speed obtained by a block-cipher-based authenticated-encryption scheme like IAPM or
OCB or generic composition with with a software-optimized MAC. Thus a stream-cipherbased authenticated-encryption scheme ought to reach for speeds of 10 cycles/byte, or faster,
until the performance-advantage starts to become attractive. If one chooses an inﬁnite-outputlength pseudorandom function that does pad-generation in roughly 5 cycles/byte, as reported
for SEAL, or 7 cycles/byte, as reported for Panama, then one has roughly 5 cycles/byte leftto spend on authenticity and still out-perform an AES-based solution. This would seem to bequite doable using an aggressively optimized MAC (recall that UMAC performs at about 1
cycle/byte).
Fundamentally, the “overhead” of MULTI-S01 (meaning the work done beyond Panama) ismore than desired because every 64 bits of message results in multiplying two GF(264 )-values,
neither of which are ﬁxed beyond the scope of a single message. A GF(264 )-multiplication
requires several cycles. To get impressive performance one will have to base the authenticityenabling calculations on something faster than a GF(264 )-multiplication of frequently-changing
values. We given an example of such a technique in the next section.

7.5

Generic composition as a better alternative

The alternative to any tightly-integrated authenticated-encryption scheme is generic composition. The generic composition paradigm has been studied in [BeNa]. Though that work did
not directly address stream ciphers, stream ciphers are no less appropriate as starting points
for generic composition.
There are three natural approaches to generic composition: encrypt-and-mac, encryptthen-mac, and mac-then-encrypt. The analysis in [BeNa] shows that encrypt-then-mac has
the most desirable security characteristics. Though the results of that paper do not directly
apply to stream ciphers, we believe that the results in [BeNa] can, all the same, be lifted to16deal with stream ciphers and that, once one does so, the overall conclusion will remain thesame: encrypt-then-mac will have the best security properties.
To use encrypt-then-mac for a stream cipher takes a bit of care. To start with, assume a message authentication code MAC : Kmac × {0, 1}∗ → {0, 1}τ . Assume that thesender and receiver share an encryption key Kenc drawn from some set Kenc , and assume
that they share a MAC key Kmac drawn from some set Kmac . Assume one has a privacyonly stream cipher in which, to encrypt a message M , the sender computes a ciphertext
C = EKenc (M ) = MakePad(state sender ) ⊕ M . The functions E and MakePad depend on, andmutate, the internal variable state sender . Likewise, to decrypt a ciphertext C, the receiver computes M = DKenc (C) = MakePad(state receiver ) ⊕ C. These functions depends on, and mutate,
the internal variable state receiver .
To modify the privacy-only Vernam cipher to provide for authenticity too, have the sendersend, instead of C, the ciphertext C  = C, MACKmac (state sender , C). Have the receiver, on
receipt of C ∗ , T ∗ , compute the expected tag T  = MACKmac (state receiver , C ∗ ). If T  = T ∗then the receiver recovers the plaintext M by M = DKenc (C). Otherwise, the decryption gives
invalid. Note that MAC generation and MAC veriﬁcation does not mutate any internal state,
and note that the scope of the MAC includes (and must include) the state which the senderand receiver maintain when using a stream cipher. Typically, this state is a counter of just a
few bytes. Assume in what follows that it is 16 bytes.
The eﬃciency of the approach above depends, almost entirely, on the eﬃciency of the MAC:
the computational overhead for authenticity is, very nearly, the computational overhead of
MACing a message having the same length as the plaintext. The question is, therefore, if one
can MAC using an overhead less than the overhead of MULTI-S01 (meaning the computational
work done by MULTI-S01 above and beyond computing the keystream).
The answer to this would seem to be yes. As an example, the UMAC message authentication code [UMAC] authenticates messages with approximately 1 cycle/byte. But one canargue that it is much more complex and less suited for hardware than MULTI-S01. Therefore
we sketch an example message authentication code (a standard Carter-Wegman MAC) morein the spirit of MULTI-S01.
Let C be the message we wish to MAC. Let paddedC = C  1  0i , where i is thesmallest value such that |paddedC| is divisible by 64. Partition paddedC into 64-bit blocks
Cm−1 · · · C1 C0 . Let the MAC key be Kmac = α  β where |α| = |β| = 64. To MAC C, compute
MACαβ (C) = AESβ (state sender ) ⊕ Hα (paddedC) whereHα (paddedC) = αm ⊕ Cm−1 ⊗ αm−1 ⊕ Cm−2 ⊗ αm−2 ⊕ · · · ⊕ C1 ⊗ α ⊕ C0
As before, ⊕ and ⊗ refer to addition and multiplication in GF(264 ). Correctness of this method
as a MAC is standard; it depends on H being a good xor-universal hash-function family.
To eﬃciently compute Hα (paddedC), start a 64-bit register A with the value 0127 1. Repeatedly take the value of A, multiply it by α, then add in (xor) the next value Ci (as one reads
left-to-right down Cm−1 · · · C1 C0 ). The computational eﬃciency of this method is better, perbyte, than multiplying two points in GF(264 ) since one of the two points, being ﬁxed for as
long as one uses the underlying authenticated-encryption key, can be preprocessed into tables
to permit more the eﬃcient computation, if desired. Indeed one could move to using GF(2128 )and still preserve eﬃciency. All in all, the generic composition approach, as sketched above,
would seem to be faster and more ﬂexible than the approach take by MULTI-S01.
17

References[BeNa]

M. Bellare and C. Namprempre. Authenticated encryption: Relations amongnotions and an analysis of the generic composition paradigm. Advances in Cryptology – ASIACRYPT ’00. Lecture Notes in Computer Science, vol. 1976, 2000.

[DEF]

Hitachi, Ltd. A Symmetric Key Encryption Algorithm: MULTI-S01 — An
Integrity-Aware Block Encryption Based on Cryptographic Pseudorandom Number Generator. Undated manuscript with copyright 2000, 2001. Note: Hitachi maintains website http://www.sdl.hitachi.co.jp/crypto/s01/index.html for information about MULTI-S01.

[EVAL]

Anonymous. Evaluation of MULTI-S01. Unpublished and conﬁdential manuscript.
January 17, 2001.

[IAPM]

C. Jutla. Encryption modes with almost free message integrity. Advances in
Cryptology – EUROCRYPT 2001. Lecture Notes in Computer Science, vol. 2045,
Springer-Verlag, 2001.

[OCB]

P. Rogaway, M. Bellare, J. Black, and T. Krovetz. OCB: A block-cipher modeof operation for Eﬃcient Authenticated Encryption. Proceedings of the 8th ACM
Conference on Computer and Communications Security (CCS-8), ACM Press, 2001.

[PANA]

J. Daemen and C. Clapp. Fast Software Encryption, 5th International Workshop(FSE ’98), Lecture Notes in Computer Science, vol. 1372, Springer-Verlag, 1998.

[SELF]

Hitachi, Ltd. Self-Evaluation Report MULTI-S01 (revised for 2001 submittion[sic]). Undated manuscript with copyright 2000, 2001.

[SLIDES] S. Furuya (Hitachi Ltd.) A stream cipher for Cryptrec: MULTI-S01. Transparencies from an undated talk, copyright 2001.
[UMAC]

J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway. UMAC:
Fast and secure message authentication. Advances in Cryptology — CRYPTO ’99.
Lecture Notes in Computer Science, vol. 1666, Springer-Verlag, 1999.

[XCBC]

V. Gligor and P. Donescu. Fast encryption and authentication: XCBC encryption and XECB authentication modes. Fast Software Encryption, Lecture Notes in
Computer Science, Springer-Verlag, 2001.

18