Sound Approximations to Diffie-Hellman utilizing Revise Rules.

Uploaded on:
Category: General / Misc
Sound Approximations to Diffie-Hellman utilizing Rework Rules Christopher Lynch Catherine Knolls Maritime Examination Lab Cryptographic Convention Investigation Formal Techniques Approach generally overlooks properties of calculation However Mathematical Properties of Calculation can be displayed as Equational Hypothesis
Slide 1

Sound Approximations to Diffie-Hellman utilizing Rewrite Rules Christopher Lynch Catherine Meadows Naval Research Lab

Slide 2

Cryptographic Protocol Analysis Formal Methods Approach for the most part overlooks properties of calculation But Algebraic Properties of Algorithm can be displayed as Equational Theory

Slide 3

Example: DH Protocol A ! B: g nA B ! A: g nB A ! B: e(h(exp(g,n B ¢ n A )),m) B ! An: e(h(exp(g,n A ¢ n B )),m’)

Slide 4

DH utilizes Commutativity (C) exp(g,n B ¢ n A ) = exp(g,n A ¢ n B ) This can prompt assaults Analysis utilizing C-unification discovers these assaults

Slide 5

C-Unification exp(g,X ¢ Y) = exp(g,n A ¢ n B ) has two arrangements Solution 1: [X  n A , Y  n B ] Solution 2: [X  n B , Y  n A ]

Slide 6

C-unification is Exponential exp(g,X 1  X n ) = exp(g,c 1  c n ) has 2 n arrangements Let d 1 ,  ,d n be a stage of c 1 ,  ,c n 2 n changes exist Then [X 1  d 1 ,  ,X n  d n ] is an answer

Slide 7

Goal of Paper Find a productive hypothesis H to estimated C soundly i.e., an assault modulo H is an assault modulo C But shouldn\'t something be said about the other way around (that’s the critical step)

Slide 8

Our Results We discovered a proficient hypothesis H which approximates C soundly We gave straightforward properties for a DH convention to fulfill We demonstrated that if a convention has these properties then a C-assault can be changed over to a H-assault

Slide 9

Basic Properties symmetric keys of structure h(exp(g,n A ¢ n B )) A genuine central can send exp(g,n) h-terms show up no place else, type nonces show up no place else, exp-terms show up no place else

Slide 10

Properties avoiding Role Confusion Attacks Messages scrambled with DH-key from Initiator and Responder must be of distinctive structure Messages encoded with DH-key must contain a remarkable strand id

Slide 11

Intruder not surprisingly, the gatecrasher can see all messages, and alter, erase and make messages obviously, the interloper does not need to comply with any of these standards

Slide 12

About the Properties Most DH-conventions for two principals fulfill these properties They are syntactic, so it is anything but difficult to check if a convention meets them

Slide 13

Who Cares? A Protocol Developer: A convention with these properties will have no assault in light of commutativity A Protocol Analyzer: If a convention has these properties, investigate it utilizing effective H-hypothesis. Just in the event that it doesn\'t, then utilize C.

Slide 14

Contents of Talk Representation of Protocol Derivation Rules Properties and Proof Techniques

Slide 15

Example of DH Protocol A ! B: [exp(g,n A ), nonce] B ! A: [exp(g,n B ), e(h(exp(g,n B ¢ n An )),exp(g,n A ))] A ! B: e(h(exp(g,n A ¢ n B )),alright)

Slide 16

Specification of Protocol Rules A: ! [exp(g,n A ), nonce] B: [Y, nonce] ! [exp(g,n B ), e(h(Y,n B ),Y)] A: [Z, e(h(exp(Z,n An ),exp(g,n A ))] ! e(h(exp(Z,n An ),alright)

Slide 17

Instantiation of Specification A: ! [exp(g,n A ), nonce] B: [exp(g,n A ), nonce] ! [exp(g,n B ), e(h(exp(g,n A ¢ n B )),exp(g,n A ))] A:[exp(g,n B ), e(h(exp(g,n B ¢ n An )),exp(g,n A ))] ! e(h(exp(g,n B ¢ n An ),alright)

Slide 18

Equation required in Protocol Need to realize that: h(exp(g,n A ¢ n B )) = h(exp(g,n B ¢ n A )) That’s where C is required, yet arrives a more effective H h(exp(X,Y ¢ Z)) = h(exp(X,Z ¢ Y)) will work, yet at the same time not adequate

Slide 19

Modification of DH Protocol Assume inititiator uses capacity h 1 and responder utilizes h 2 A ! B: [exp(g,n A ), nonce] B ! A: [exp(g,n B ), e(h 2 (exp(g,n B ¢ n An )),exp(g,n A ))] A ! B: e(h 1 (exp(g,n A ¢ n B )),alright)

Slide 20

New Specification A: ! [exp(g,n A ), nonce] B: [Y, nonce] ! [exp(g,n B ), e(h 2 (Y,n B ),Y)] A: [Z, e(h 1 (exp(Z,n An ),exp(g,n A ))] ! e(h 1 (exp(Z,n An ),alright)

Slide 21

New Instantiation A: ! [exp(g,n A ), nonce] B: [exp(g,n A ), nonce] ! [exp(g,n B ), e(h 2 (exp(g,n A ¢ n B )),exp(g,n A ))] A:[exp(g,n B ), e(h 1 (exp(g,n B ¢ n An )),exp(g,n A ))] ! e(h 1 (exp(g,n B ¢ n An ),alright)

Slide 22

Equation we now require h 2 (exp(x,n A ¢ n B )) = h 1 (exp(x,n B ¢ n A )) So hypothesis H can\'t avoid being h 2 (exp(X,Y ¢ Z)) = h 1 (exp(X,Z ¢ Y))

Slide 23

How Efficient is H Using results from [LM01], we see that: In H, every single unifiable term have a most broad unifier Complexity of H-unification is quadratic (normally direct by and by)

Slide 24

Completeness Theorem C hypothesis is presently exp(X,Y ¢ Z) = exp(X, Z ¢ Y) and h 1 (X) = h 2 (X) Show that any assault modulo C can be changed over to assault modulo H

Slide 25

Differences in the middle of H and C h 1 (exp(g, n 1 ¢ n 2 )) squares with h 2 (exp(g,n 1 ¢ n 2 )) modulo H yet not modulo C h 1 (exp(g, n 1 ¢ n 2 )) measures up to h 1 (exp(g, n 2 ¢ n 1 )) modulo H yet not modulo C h 1 (exp(x, n 1 ¢ n 2 ¢ n 3 )) rises to h 2 (exp(x, n 3 ¢ n 2 ¢ n 1 )) modulo H yet not modulo C

Slide 26

Protocol Instance A Protocol Instance has 2 sections Protocol Rules Derivation Rules to speak to Intruder

Slide 27

Derivation Rules [X,Y] ` X [X,Y] ` Y X, Y ` [X,Y] privkey(A), enc(pubkey(A), X) ` X pubkey(A), enc(privkey(A), X) ` X

Slide 28

More Derivation Rules X, Y ` enc(X,Y) X, Y ` e(X,Y) X ` h i (X) X, e(X,Y) ` Y X,Y ` exp(X,Y)

Slide 29

Derivation modulo C Recall guideline X, e(X,Y) ` Y Derivation modulo C: X 1 e(X 2 ,Y) ` CH Y if X 1 = C X 2

Slide 30

Example h 1 (exp(x,n B ¢ n I ¢ n A )), e(h 2 (exp(x,n A ¢ n I ¢ n B )),m) ` C m But not h 1 (exp(x,n B ¢ n I ¢ n A )), e(h 2 (exp(x,n A ¢ n I ¢ n B )),m) ` H m

Slide 31

How to change over from ` C to ` H Requires Certain Properties Use Rewrite System R so that S ` C m infers S + R ` H m + R: exp(X,Y) ! X if Y is not a genuine important nonce

Slide 32

Properties of Protocol hashed symmetric keys are of the structure h(exp(X ¢ n)), where X in the long run brings together with a term exp(g,n’) h-terms show up no place else, type nonces show up no place else, exp-terms show up no place else

Slide 33

More Interesting Properties A message scrambled with h 1 - term on RHS of convention can\'t bind together with message encoded with h 2 - term on LHS Avoids part disarray assaults Messages encoded with hashed term must incorporate a strand id in message Avoids assaults including distinctive occurrences of same convention or diverse conventions

Slide 34

Properties of Derivable Terms Honest Principals take after Protocol Rules But Intruder can utilize inference tenets to make terms which defy properties Nevertheless, we demonstrate that sure properties are safeguarded by determination and convention rules

Slide 35

Example Properties of Derivable Terms There is a set N (legitimate main nonces) Elements of N just show up as type If a term exp(g,t 1  t n ) is resultant t 1 and t n are in N or are logical t 2 ,  ,t n-1 are logical if term is not a key, then t n logical

Slide 36

More Properties There are numerous more properties Some very muddled And numerous lemmas and hypotheses to demonstrate them

Slide 37

Properties Imply Every term will decrease by R to a term with at most two types (all types not in N are evacuated by revise leads) This and different properties suggest that if s and t C-bring together then s + R and t + R H-bring together

Slide 38

Summary Suppose a DH-convention obeys basic (simple to check) properties Then it’s conceivable to find assaults taking into account commutativity, utilizing a productive equational hypothesis

Slide 39

Related Work Properties so assaults displaying cancelation of encryption/decoding standards are found with free variable based math Symmetric Key [Millen 03] Public Key [LM 04]

Slide 40

Future Work Other DH wor

View more...