[17] Chokhani, S. and W. Ford (1999). Internet X.509

Directory”Public Key and Attribute Certi¬cate

Public Key Infrastructure Certi¬cate Policy and

Frameworks.

Certi¬cation Practices Framework. RFC 2527.

[18] Boeyen, S., T. Howes, and P. Richard (1999). Inter-

net X.509 Public Key Infrastructure Operational

Protocols”LDAPv2. RFC 2559.

SELECTIVE FORGERY

[19] Myers, M., R. Ankney, A. Malpani, S. Galperin, and

C. Adams (1999). X.509 Internet Public Key In-

Selective forgery is a message related forgery

frastructure Online Certi¬cate Status Protocol”

against a cryptographic digital signature scheme.

OCSP. RFC 2560.

Given a victim™s verifying key, a selective forgery

[20] Housley, R. and P. Hoffman (1999). Internet X.509

Public Key Infrastructure Operational Protocols: is successful if the attacker ¬nds a signature s for

FTP and HTTP. RFC 2585. a message m selected by the attacker prior to the

[21] Boeyen, S., T. Howes, and P. Richard (1999). In- attack, such that the signature s is valid for m with

ternet X.509 Public Key Infrastructure LDAPv2 respect to the victim™s verifying key.

Schema. RFC 2587.

[22] Housley, R. (1999). Cryptographic Message Syntax. Gerrit Bleumer

RFC 2630.

[23] Rescorla, E. (1999). Dif¬e-Hellman Key Agreement

Method. RFC 2631.

SELF-SHRINKING

[24] Ramsdell, B. (ed.). (1999). S/MIME Version 3 Cer-

ti¬cate Handling. RFC 2632.

GENERATOR

[25] Ramsdell, B. (ed.). (1999). S/MIME Version 3 Mes-

sage Speci¬cation. RFC 2633.

The self-shrinking generator is a clock-controlled

[26] Hoffman, P. (ed.). (1999). Enhanced Security Ser-

generator that has been proposed in [1]; it is

vices for S/MIME. RFC 2634.

[27] Ellison, C. (1999). SPKI Requirements. RFC 2692. strongly related to the shrinking generator, but

[28] Ellison, C., B. Frantz, B. Lampson, R. Rivest, B. uses only one Linear Feedback Shift Register

Thomas, and T. Ylonen (1999). SPKI Certi¬cate (LFSR) R, producing a maximum-length linear se-

Theory. RFC 2693.

quence.

[29] Myers, M., X. Liu, J. Schaad, and J. Weinstein

Its principle is really easy to get: the output se-

(2000). Certi¬cate Management Messages over

quence of the LFSR is partitioned into pairs of bits.

CMS. RFC 2797.

According to the value of the pair, one bit is added

[30] Rigney, C., S. Willens, A. Rubens, and W. Simpson

to the keystream, and then the pair is discarded

(2000). Remote Authentication Dial in User Ser-

and we go to the next one. More precisely:

vice (RADIUS). RFC 2865.

[31] Rigney, C. (2000). RADIUS Accounting. RFC 2866.

[32] Rigney, C., W. Willats, and P. Calhoun (2000). Pair Bit added

RADIUS Extensions. RFC 2869.

[33] Mitton, D. (2000). Network Access Servers Requi- 10 0

rements: Extended RADIUS Practices. RFC 2882. 11 1

[34] Santesson, S., W. Polk, P. Barzin, and M. Nystrom 01 no bit added

(2001). Internet X.509 Public Key Infrastructure 00 no bit added

Quali¬ed Certi¬cates Pro¬le. RFC 3039.

Semantic security 559

EXAMPLE. Let us consider that R has length four, error in a ciphertext on about t bits of plaintext, it

and that its feedback is given by st+1 = st + st’3 . If is more dif¬cult for an attacker to forge a plaintext

the initial state is s0 s1 s2 s3 = 1010, then the output of its choice than in a synchronous stream cipher.

of the LFSR is 101011001000111101011001000- Moreover, it is also more dif¬cult for him to desyn-

1111010110010001111 . . . This gives the following chronize the keystream, since the scheme is able

output for the whole scheme: 00101101001011 . . . to resynchronize it by itself. If the attacker wants

to desynchronize all the keystream, he has to do

A recent survey on the possible attacks is [2]. a lot of modi¬cations on the ciphertext. Neverthe-

less, some complementary mechanisms, that can

Caroline Fontaine

ensure authentication or integrity of the cipher-

text are welcome to help the receiver check that

References

all is going well.

At last, since each plaintext digit in¬‚uences the

[1] Meier, W. and O. Staffelbach (1995). “The self-

whole ciphertext (through the feedback of the ci-

shrinking generator.” Advances in Cryptology”

phertext on the keystream generation), the statis-

EUROCRYPT™94, Lecture Notes in Computer Sci-

tical properties of the plaintext are dispersed in

ence, vol. 950, ed. A. De Santis. Springer-Verlag,

the ciphertext, and such a scheme may be more

Berlin, 205“214.

resistant against attacks based on plaintext re-

[2] Zenner, E., M. Krause, and S. Lucks (2001). “Im-

proved cryptanalysis of the self-shrinking genera- dundancy, than synchronous stream ciphers.

tor.” ACIPS 2001, Lecture Notes in Computer Sci- Good references are [1] and [2].

ence, vol. 2119, eds. V. Varadharajan and Y. Mu.

Springer-Verlag, Berlin, 21“35. Caroline Fontaine

References

SELF-SYNCHRONIZING

[1] Maurer, U.M. (1991). “New approaches to the de-

STREAM CIPHER sign of self-synchronizing stream ciphers.” Ad-

vances in Cryptology”EUROCRYPT™91, Lecture

In a self-synchronizing, or asynchronous, stream Notes in Computer Science, vol. 547, ed. D.W.

cipher, the keystream depends on the secret key of Davies. Springer-Verlag, Berlin, 458“471.

[2] Rueppel, R.A. (1986). Analysis and Design of

the scheme, but also of a ¬xed number, say t, of ci-

Stream Ciphers. Springer-Verlag, Berlin.

phertext digits (that have already been produced,

or read; this distinguishes it from a synchronous

stream cipher). It can be viewed as follows:

SEMANTIC SECURITY

key key

ciphertext

Semantic security is a notion to describe the secu-

plaintext plaintext

rity of an encryption scheme.

ENCRYPTION DECRYPTION

An adversary is allowed to choose between two

According to its design, such a scheme is able plaintexts, m0 and m1 , and he receives an encryp-

to resynchronize the keystream with the message tion of either one of the plaintexts. An encryp-

with just a few correct bits of ciphertext. This tion scheme is semantically secure, if an adver-

means that if some bits are inserted or deleted sary cannot guess with better probability than 1/2

in the ciphertext, just a small part of the plain- whether the given ciphertext is an encryption of

text will not be obtained correctly; the next set of message m0 or m1 . The notion is also referred to

t consecutive correct bits in the ciphertext will be as indistinguishability of encryptions and noted as

suf¬cient to resynchronize the keystream and pro- IND. Historically the word “semantic” came from

duce the following bits of the plaintext correctly. the de¬nition that the encryption reveals no in-

Let us now consider that one bit of the cipher- formation no matter what kind of semantics are

text has been altered during the transmission. embedded in the encryption. It has been proven

This will induce some errors in the decryption of that the de¬nition describing this requirement is

the next t bits; after this, decryption will go on equivalent to the indistinguishability of encryp-

correctly. tions. The notion of semantic security can be fur-

What can an active attacker do with such a ther distinguished by the power of adversary. More

scheme? According to the propagation of each speci¬cally, a powerful adversary may have access

560 Sender anonymity

to an encryption oracle and/or decryption oracle tell with better probability than pure guessing

at various stages of the guessing game. Here, an who sent the messages. During the attack, the

encryption oracle is an oracle that provides an en- eavesdropper may also listen on all communica-

cryption of a queried plaintext, and a decryption tion lines of the network including those that con-

oracle provides the decryption of a queried cipher- nect the potential senders to the network and he

text (see also random oracle model). may send his own messages. It is clear that all

The notion of semantic security can be applied messages in such network must be encrypted to

to both symmetric cryptosystems and public key the same length in order to keep the attacker from

cryptosystems. But since the concrete security distinguishing different messages by their content

analysis of a public key encryption scheme is more or length. The anonymity set for any particular

tractable, the term is more frequently used to dis- message attacked by the eavesdropper is the set

cuss the security of public key encryption schemes. of all network participants that have sent message

In a public key encryption scheme, the adver- within a certain time window before the attacked

sary can always access the encryption oracle, be- message was received. This time window ofcourse