Transcript Information Theory and Security

Security Models: Dolev-Yao,
Semantic Security, Probabilistic
Encryption and ZKIP
Dolev-Yao

For distributed systems and networks, we often should assume that there are
adversaries
– Everywhere in the network
– Adversary may: eavesdrop, manipulate, inject, alter, duplicate, reroute,
etc…
– Adversary may control a large number of network nodes that are
geographically separated

Dolev-Yao Threat Model:
– A very powerful adversarial model that is widely accepted as the standard
by which cryptographic protocols should be evaluated
– Eve, the adversary, can:




Obtain any message passing through the network
Act as a legitimate user of the network (i.e. can initiate a
conversation with any other user)
Can become the receiver to any sender
Can send messages to any entity by impersonating any other entity
Dolev-Yao, pg. 2

This seems very powerful, but not entirely so…

Under Dolev-Yao:
– Any message sent via the network is considered to have been sent by Eve
– Thus, any message received “might” have been manipulated by Eve
– Eve can control how things are sent

What is not possible:
– Eve cannot guess a random number which is chosen as part of a security
protocol
– Without knowledge of a key, Eve cannot figure out a plaintext from a
ciphertext, nor can she create ciphertexts from a plaintext.
– Eve can’t solve the private-key pairing of a public key
– Eve cannot control the “memory” of a computing device of a legitimate
user (i.e. Eve can only play with the communication)
Strong Security Definitions

Generally, when discussing the crypto algorithms in this class,
we have considered a weak confidentiality model, in which our
enemy was a passive eavesdropper

For real applications, however, we should consider an active
adversary also– they may modify a ciphertext or calculate a
plaintext and send the result to a user to get an oracle service

Oracle service: A principal is used as an oracle when the
principal performs a cryptographic operation inadvertantly for
the attacker

We should anticipate that Eve is an active adversary who is
clever, and can set up Oracle services
Strong Security Definitions, pg. 2

Further, in many applications, the plaintext messages contain
easy-to-guess information (e.g. a beginning of an email, or some
fields of some type of form, or commands to a receiver)

This is problematic:
– To guess, Eve need only encrypt the plaintext herself and see if the
result matches a received ciphertext
– This is a problem with textbook-style crypto.
Returning to Attack Models from Day 1

Chosen Plaintext Attack (CPA): An attacker chooses plaintext
messages and gets encryption assistance to obtain the
corresponding ciphertext messages. The task for the adversary is
to weaken the cryptosystem using the plaintext-ciphertext pairs.

Chosen Ciphertext Attack (CCA): An attacker chooses
ciphertext messages and gets decryption assistance to obtain the
corresponding plaintext messages. Objective is to weaken the
cryptosystem. The attacker is successful if he can retrieve some
secret plaintext information from a target ciphertext which is
given to the attacker after the decryption assistance is stopped.

Adaptive Chosen Ciphertext Attack (CCA2): A CCA where the
decryption assistance will be available forever, except for the
target ciphertext.
Attack models further discussed


Note 1: Encryption assistance of a public key system is always
available since the public key is always available… In
otherwords, CPA can always be mounted against a public key
system. Hence all public key systems *should* resist CPA!!!
Note 2: Attackers may exploit the nice homomorphic properties
of public key systems to make up a ciphertext via some clever
calculations.
– If the attacker is assisted by a decryption service, then
manipulations may enable him to obtain some plaintext
information
– One must be careful whether one is “used” to provide a decryption
oracle
– Where do we see this problem? Answer: challenge response and
nonces!!!
What does it mean to be secure?

For a PK encryption algorithm, some starting points:
– It means that recovering the private key from the public key
should be hard
– With high probability, a message should not be recovered from
seeing its encrypted form
– No useful information can be computed from the encrypted form
of a message
– We do not want the adversary to be able to compute useful facts
from just seeing messages (i.e. that two messages are of identical
content)
Polynomial Time Indistinguishability

Polynomial Indistinguishability: An encryption scheme is
polynomial time indistiguishable if no adversary can find two
messages whose encryptions he can distinguish between
– I.e. if ciphertexts are like messages in an envelope, we can’t tell
two envelopes apart
– Or, it is impossible (in polynomial in k-bits) to find two messages
m0 and m1 such that a polynomial-time algorithm can distinguish
between c0 and c1

Note: Any encryption algorithm in which the encryption
algorithm is deterministic immediately fails
– i.e. given f, m0 and m1, and c coming from either m0 or m1, it is
easy to decide which one it came from (just calculate f(m0) and
f(m1)
Semantic Security







Consider two games, and let h:M  {0,1}* where M is a message space. E.g.
h() may be any function that finds information about m from M (e.g. does m
have an “e” in it?)
Game 1: We tell Eve that we are about to choose m and ask her to guess h(m)
Game 2: We tell Eve a=E(m) for some m, and ask her to guess h(m)
In first game: the adversary only knows that a message m is about to be
chosen
In second game: the adversary sees a ciphertext.
Semantic Security: The probability of winning Game 1is the same as the
probability of winning Game 2.
– i.e. the adversary should not gain any advantage or information from
seeing the ciphertext
Again, this implies that E() must not be deterministic, otherwise Eve would
calculate E(0…0), E(0…1), … E(1…1), see which matched c, and then
calculate h(m) on her own
SRA Mental Poker


Suppose Alice lives in one town and Bob lives in another, they
would like to play poker over the phone.
To do this, though, they would like to have some digital way of
accomplishing this
– Cards are encoded into messages so that the card game can be
played in communications
– Cards must be dealt fairly:




1) Deal must distribute all hands with equal probability
2) Alice and Bob must know the cards in their own hand, but
not in another’s hands
3) Alice and Bob must be viewed as potential cheaters who
cannot be relied upon
4) Alice and Bob should both be able to verify that a preceding
game was played fairly
SRA Mental Poker, pg. 2



The idea behind this was originally proposed by Shamir, Rivest,
and Adleman
Makes use of commutative ciphers (e.g. RSA): A message can
be doubly encrypted by Alice and Bob and the result does not
depend on the order: EA(EB(M)) = EB(EA(M))
Protocol: Suppose (for simplicity) we have three cards M1, M2,
M3
– Alice encrypts the three cards as Ci=EA(Mi). She sends Bob these
three ciphertexts in a random order
– Bob picks at random one ciphertext (C), he double encrypts to get
CC= EB(C), and also picks another C’ and sends both to Alice.
– Alice decrypts both CC and C’. Decryption of C’ is her hand,
decryption of CC is C’’ which is sent to Bob
– Bob decrypts C’’ and thereby obtains his hand.
SRA Mental Poker, pg. 3

Suppose that the encryption algorithm is strong– this will not
mean that the poker game is really strong. In fact, the fact that
an adversary (given a plaintext) without the correct encryption
key cannot create a valid ciphertext, will not mean “secure”.

The SRA protocol:
– 1) Alice and Bob do obtain a hand (1 card) with equal probabilities
because Alice shuffles in step 1. Note: Alice wants to shuffle
uniformly, otherwise Bob would have an advantage since he
selects.
– 2) Each of the two parties knows his own hand after double
decryption, but does not know the other hand.
– 3) The protocol does not rely on any party to be honest.
SRA Mental Poker, pg. 4

Property 4 (Fairness) is harder than it looks... Look at the Shamir proposal,
which used a variation of RSA, where both parties share the same N but keep
their encryption+decryption exponent private until after the game is over to
verify the game.

Let N be shared RSA modulus, and exponents (eA, dA) and (eB, dB). Here
EX(M) = MeX.

Before completing the game, both parties keep their encryption and
decryption exponents secret. Thus, no one can create a valid ciphertext which
has been created by the other party. Also, neither party can decrypt a
ciphertext which has been created by the other party. Thus, the cryptosystem
is “kind of strong”.

After the game finishes, both parties can disclose their encryption and
decryption exponents to the other party, and they can verify that no cheating
was performed anywhere… so (4) works
SRA Mental Poker, pg. 4






But strong is not strong enough– an attacker’s inability to create a valid ciphertext
from a given plaintext without the correct encryption key, or decrypt without the
correct decryption key
Why? Lipton’s attack shows why… the cryptosystem is unable to hide certain a priori
information in the plaintext…
A number a is a quadratic residue modulo N if gcd(a,N) =1 and there is an x such that
x2 = a mod N
Note that e and d must be odd (since f(N) is even)
M is a quadratic residue modulo N iff the ciphertext is also a quadratic residue
modulo N
– C = Me = (x2)e = (xe)2 mod N
– Knowing factorization of N (which both parties do) allows for easy determination
of whether something is a quadratic residue (calculate Legendre symbols)
– Thus, if some card a quadratic residue, then a party who knows this fact will have
an advantage in the game… (unless all cards are quadratic residues)
Thus the mental poker game is not secure against “chosen plaintext attack” (where
adversary cleverly chooses the plaintext to represent the card)
Enter Probabilistic Encryption

In order to have semantic (or indistinguishability) security, we
must abandon the trapdoor and deterministic model of public
key crypto

Probabilistic encryption:
– Still assumes the existence of a trapdoor
– We begin (and end) by securely encrypting single bits
Probabilistic Encodings

A powerful approach to secret dissemination uses probabilistic encryption
(similar idea in Wyner codes)

Let f(x) be a trapdoor function and G(x) a hardcore predicate for f(x) (i.e.
hard to calculate G(x) from just f(x) )

A probabilistic encryption procedure is:
Dissemination: Probabilistic Encodings (Wyner)

Applying this idea:
– Take G(x)=m to be the parity
function of x
1.
Alice wants to send m=0 or 1 to Bob
She chooses a random x of length N
such that G(x)=m
Transmits x to Bob
2.
3.


Assuming pAB=0, then Bob
recovers m by calculating G(x)
For large N, the probability of an
odd amount of bit errors is




0.5 1  1  2p E   0.5
More generally, apply ECC across
m’s to handle pAB not 0
This method needs pAB < pE !
N
Non-Malleable Cryptography Model

Non-malleable cryptography strengthens the notions of (public
key) cryptography: it should not be possible for Eve to modify a
plaintext message in a meaningfully controllable manner via
modifying the plaintext
– The usual Dolev explanation: Suppose you have two companies
making a bid for a contract. If company A sends in a bid for X
dollars by sending EA(X), and B can intercept, modify this to
produce EA(Y) in a meaningful manner, and forward then B will
have a bidding advantage.

We have seen such a problem before:
– One-time pads and Vernam ciphers: it is possible to modify select
bits
– We saw this type of weakness in WEP
Malleability Attacks

In a malleability attack, Eve’s objective is, given a ciphertext C,
not to learn something about the plaintext M, but instead to
wreak havoc upon the eventual decoding
– Eve needs to create a relationship C C’ that results in a
meaningful relationship M M’

Problem: Most conventional cryptographic algorithms are the
result of trapdoor functions
– Partial information oracles exist for these public key schemes (e.g.
the math that lets one learn parity can be the basis for conducting a
malleability attack)

Example: How to double a plaintext in RSA encryption
– Take C=Me mod N and then produce C’ = C2e mod N
Byzantine: What comes after Dolev-Yao

The Dolev-Yao model is the foundation of security analysis for active
adversary scenarios, but does not capture everything that an adversary can
do:
– It does not involve entity compromise

In situations involving many participants (e.g. distributed computing or peerto-peer), it is natural to ask what can happen if a legitimate entity becomes
compromised

A Byzantine failure is one where a node/entity fails to operate properly, but
continues to operate (as opposed to fail-stop failures)

Example Byzantine Failures:
– A node may lie about connectivity
– Flood network with false traffic
– Falsely describe opinions of another node (e.g. P2P)
– Capture a strategic subset of devices and collude
How to Cope with Byzantine Behavior

General Strategies for coping with Byzantine :
– 1) Need to assure there is at least reliable information then issue
becomes discerning between good and bad information


Statistical robustness, modeling and outlier filtering
Ensure that there are multiple sources of information
– 2) Failure detection

Setup protocols to identify who is not trustworthy
– 3) Resource reservation and fairness

Make sure that every entity gets its fair share of resources, in
spite of being bad… prevents greedy behavior
– 4) Multipath flows and service replication
– 5) Distribute information and require cooperation to prevent
information exposure

Threshold cryptography
Case Study: Robust Flooding

Flooding: Each router R that receives a packet from neighbor N forwards the packet
to each neighbor.
– Flooding looks like it has the properties we want
– A packet from S will reach D, provided S and D are connected by at least one
correctly functioning path, regardless of arbitrary Byzantine behavior of routers
and links not on that path, provided the network has infinite capacity.

Why “provided the network has infinite capacity?”
– Prevent Byzantine nodes from flooding network with bogus (though maybe
cryptographically legitimate) traffic

Reality: Networks have finite capacity, so we need fair allocation of resources
– Computation in routers require devices to have CPU rates better than link line
rates
– Memory in the routers  each device sets up internal queues for each potential
source along with authenticated sequence numbering… then queues are fairly
processed in round-robin manner
– Bandwidth on the links  cycle through each buffer, and transmit packets from
queues in a fair manner
Zero Knowledge Interactive Proofs

The basic idea:
1.
Alice says she has a key to the
door in the cave but does not
want to show Bob
Alice proves she has the key by
entering the cave, choosing a
random direction to go, and
waits near the door
Bob then comes to cave entrance
and asks Alice to come out a
“random side” of the cave
(left/right)
If Alice has the key, then she can
always come out the correct side
If Alice does not have the key,
she can only succeed 50% of the
time
The proof: repeat this process
many times
2.
3.
4.
5.

ZKIP: Mathematical Version

Let n=pq, and y be a square mod n.

It turns out that finding square roots mod n is equivalent to
factoring n

Suppose Peggy, the prover, wants to prove that she knows a
square root s of y but she does not want to reveal s.

1) Peggy chooses random numbers r1 and r2 with r1r2 = s mod n

2) Peggy calculates x1 = (r1)2, x2=(r2)2 mod n and sends these to
Victor, the verifier

3) Victor checks that x1x2 = y mod n. He chooses either x1 or x2
and asks Peggy to produce a square root of it

4) The process is repeated several times until Victor is happy
ZKIP, pg. 2

Clearly, if Peggy knows s, there is no problem.

If Peggy does not, then she can still send x1 and x2

If she knows a square root of x1 and a square root of x2, then she knows a
square root of y ≡ x1x2. Therefore, for at least one of them, she does not know
a square root.

At least half the time, Victor is going to ask her for a square root she doesn’t
know. Since computing square roots is hard, she is not able to produce the
desired answer, and therefore Victor finds out that she doesn’t know s.

Suppose, however, that Peggy predicts correctly that Victor will ask for a
square root of x2. Then she could have chosen a random r2, compute x2 ≡ r22
(mod n), and let x1 ≡ yx2−1 (mod n). She would then send x1 and x2 to Victor,
and everything works.

This method gives Peggy a 50% chance of fooling Victor on any given
round, but it requires her to guess which number Victor will request each
time. As soon as she fails, Victor will find out that she doesn’t know s.