Digital Signatures

By Hesham El-Sawaf

Digital Signatures

By Hesham El-Sawaf

AGENDA

El Gamal algorithm for digital signatures

01

02

03

Solving the discrete logarithm problem

Can we forge a digital certificate?

- Calculate some hash of the document.

El Gamal Algorithm

Note: This of course implies you have a public key too.

- What do we mean by digitally signing a document?

- Use your private key* to encrypt that hash value.

- Go public! Share your signature alongside the document as an encrypted block.

- Then what?!

- Use the public key to extract the hash from the encrypted block.

- Compare with the one you calculate.

DSS and El Gamal

Note: Dr. Taher Elgamal

- We need a standard definition...

- Digital Signature Standard (DSS).

- Set by the National Institute of Standards and Technology (NIST).

- Based on the famous ElGamal algorithm for constructing the digital signature of a document.

- Based upon the security of the one-way function of exponentiation in modular rings.

- Security?

- Difficulty of solving the discrete logarithm problem.

**El Gamal Algorithm**

Signing Protocol - initial setup

Alice chooses a large prime **p** and a primitive root **α**

**1.**

She then chooses a secret integer **z** and calculates

**β ≡ αz (mod p)**.

**2.**

The values of **p**, **α** and **β** are made public and **z** is kept private.

**3.**

**El Gamal Algorithm**

The boring stuff

1. She selects a secret random integer **k** such that **GCD(k, p – 1)** **= 1**.

2. She then computes **r ≡ αk (mod p)**.

3. She then finally computes **s ≡ k¯¹(m – zr) (mod p – 1)**.

4. The signed message is the triplet** (m, r, s)**.

× In order to **sign the message** **m**, Alice follows the steps below:

× **The verification process** can then be performed by Bob using public information only

1. Bob computes **V ≡ β r (mod p) **and** V ≡ αm (mod p)**.

**1**

**r**

**s**

**2**

2. The signature is declared valid if and only if **V ** **≡ V (mod p)**.

**1**

**2**

- Correctness?

**El Gamal Algorithm**

Example

- Suppose that the message to be signed is numerically encoded so that m = 15. Alice chooses the prime p = 71 with primitive root α = 7. Her secret integer is z = 16 therefore the calculation of β is as follows:

β ≡ α z ≡ 7 ≡ 19 (mod 71)

16

- Alice then publishes (p, α, β) as (71, 7, 19).

- After this initial setup, Alice's signing protocol begins by choosing the random integer k = 31 such that it is coprime to p - 1 = 70. She then computes r as below.

r ≡ α k ≡ 7 ≡ 11 (mod 71)

31

**El Gamal Algorithm**

Example continued...

s ≡ k (m − z r) ≡ 61 (15 − 16 ⋅ 11) ≡ 49 (mod 70)

-1

- She may then compute the message signature s.

- The signature will therefore be the triplet (m, r, s) = (15, 11, 49). Bob is then able to check the validity of this signature by the following congruences

V ≡ β r ≡19 ⋅ 11 ≡ 23 (mod 71)

1

r

s

11

49

V ≡ α ≡ 7 ≡ 23 (mod 71)

2

m

15

- Since V ≡ V (mod 71) the signature is declared valid.

1

2

**El Gamal Algorithm**

Final Notes

- The random number K is specific to each signature, the ElGamal algorithm give you the ability to create one-time signatures.

- If your laptop were to be stolen for instance, the thief would not be able to recreate a specific signature you made in the past even if he/she gained access to your private key Z.

- Careful though not to leak out the integer K, since otherwise your private key will be easily compromised from your signature and from all the other info. you make public. (Lec 14)

- The DSS is described in the document FIPS 186-3 that can be downloaded from here

**The Discrete Logarithm**

Boring stuff...

- But what about Security?!

- Just solve the equation , for s for given values of g and k.

**g = k mod p**

**s**

- Solving for s is the famous

** discrete logarithm problem**.

- Brute force...

- Calculate for i = 0, 1, 2, ... untill you find a solution.

**g **,

**i**

- Complexity is proportional to p. If p requires an n-bit representation, then the complexity, being proportional to 2 , grows exponentially with the size of p in bits.

**n**

**The Discrete Logarithm**

More boring stuff...

- A more efficient Brute force...

**Baby-step Giant-step method**

- Baby steps: Compute, sort, and store the elements g , g , g , . . ., g in a table.

**m**

**0**

**1**

**2**

**m**

- Giant steps: compute and check to see if it is in the above table.

**k**

**_____**

**m**

**g**

- If not, compute , and check to see if it is in the table.

**_____**

**2m**

**g**

**k**

- If not, repeat until you find a j so that , is in the table.

**_____**

**g**

**k**

**jm**

- Say we found = g , for some i and j.

**_____**

**g**

**k**

**jm**

**i**

- Then

**S = jm + i**

- Time complexity is O(p/m). But memory is O(m)!

- Overall complexity is O(p) = O(2 ), which is still exponential in n, the size of p.

**n**

**The Discrete Logarithm**

Pollard - ρ method

- A second approach is known as the Pollard − ρ method.

- This method is based on the assumption that g can serve as the generator of a subgroup of prime order q within Zp . That means that the set {g , g , . . .} would form a subgroup within the set Zp .

- Another concept that the P ollard−ρ method is based on is Floyd's cycle finding algorithm.

**0**

**1**

- The function -- , is assumed to be random-looking and thus is likely to enter into a loop after approximately √(π |A| / 8) and so is the average length of the cycle.

LOADING AWESOME

**The Discrete Logarithm**

Pollard - ρ method continued...

LOADING AWESOME

**The Discrete Logarithm**

Pollard - ρ method continued...

LOADING AWESOME

LOADING AWESOME

LOADING AWESOME

- Two other methods are the Pollard − λ method and the Index-Calculus method

**Forging a Certificate**

Some history

- Can we really forge a certificate issed by a CA?

- The short answer is Yes!

- In mid-2008, it was shown by a group of security researchers how the weak collision resistance property of the MD5 hashing function could be exploited to construct a forged certificate.

- They acquired some real certificates from a root CA and then proceeded to attach the CA’s signature to a different public-key embedded in a digital document whose MD5 signature was the same as that in one of the legal certificates.

**Forging a Certificate**

More history

- The reseller used cleartext-based password authentication for folks filling out CSR (Certificate Signing Request) forms.

- The attacker used this weakness to break into the reseller’s account and created for himself a new user account with authorization to issue Comodo certificates.

- The attacker then proceeded to create Comodo-signed forged certificates for the domains:
*mail.goggle.com*,*www.google.com*,*login.yahoo.com*,*login.skype.com*,*addons.mozilla.org*and*login.live.com*.

- Technically speaking, these certificates were forged because the attacker held the private keys corresponding to the public keys signed by the Comodo’s private key. This would have allowed the attacker to act like Google, Yahoo, Skype, etc.

- This unauthorized issuance of certificates was discovered within hours and these certificates revoked immediately.

**Forging a Certificate**

Enough history

- Let’s say we have created or obtained a forged certificate for the domain
*www.citibank.com*.

- The real question is, what harm may we bring to bear on the organizations whose certificate we have forged?

- We then proceed to create a Citibank look-alike web site and attache the forged certificate with this rogue site.

- Sounds like a plan, but a useless one. Why?

- In order to direct client traffic to our rogue website, we would need to poison the DNS cache likely to be used by the client applications. (Lec 17)

- Dan Kaminsky demonstrated how vulnerable DNS servers were to cache poisoning exploits, after that a majority of the world’s DNS servers have been patched and are protected against such exploits.

**Forging a Certificate**

Enough history

- So the odds are against us succeeding with cache poisoning — unless of course we have ISP and/or state level cooperation.

- So what do we do? old school.

- We could direct unsuspecting users to our rogue webserver through phishing attack. (Lec 17)

- Phishing is online fraud that attempts to steal sensitive information such as usernames, passwords, and credit card numbers.

- A common way to do this is to display familiar strings like
*www.amazon.com*or*www.paypal.com*in the browser window while their actual URL links are to rogue web servers.

**Forging a Certificate**

Hands-on

- It is easy to make yourself a “fake” root CA with the help of the opensource library called
*OpenSSL*

- A self-signed “Root CA Certificate” can be created as follows:

openssl req -new -x509 -keyout private/CAkey.pem -out CAcert.pem -days 365

- All you have to do is to somehow get innocent parties to add this certificate to the collection of root certificates already in their computers.

- A social engineering attack might be handy. (Lec 30)

- Set up an e-commerce business that uses certificates signed by you in your capacity as a root CA.

- Lure customers to your e-commerce website with deals they cannot resist. Should there be folks who take the bait and upload their credit card information to your website, just imagine how quickly you could become rich.

DO YOU HAVE ANY QUESTIONS?

**FOR LISTENING**

**THANK YOU!**