crypto slide for students, check out the good article

aaaa

1. Cryptography
Dr. A. Clune
The Computing Service
University of York

2. Outline
●
Code v Ciphers
●
Some simpler ciphers
●
Public-key cryptography
●
Digital Signatures
●
Message digests
●
Examples – digital voting, digital cash
●
Problems

3. Codes v Ciphers I
●
A Code is a non-algorithmic way of hiding a
message
–e.g. Alice and Bob agree in advance that “radish” will
mean “meet for a beer at 9pm in the Lendal Cellars”
●
Unbreakable
●
Not practical for most uses since the list of
words/phrases must be agreed in advance and is
fixed
●
How do you safely swap the code list?

4. Codes v Ciphers II
●
A Cipher is an algorithmic way of encoding a
message
●
Oldest example is the Caesar cipher:
A->D, B -> E etc.
●
This is what most people think of when they say “a
message was in code”
●
Can be broken if algorithm is flawed. The
study/practice of this is called “cryptanalysis”

5. Secrets
●
Simple ciphers rely for security on a “shared secret”.
In the Caesar example (a -> d), the secret is the
offset - “3”.
●
This secret must be known in advance by all parties
and shared, but now we can encode any message not
just phrases known in advance.
●
A good cipher relies only on the secrecy of the key,
not the secrecy of the algorithm
●
Public-key crypto helps to solve this problem

6. Some Jargon
●
The message that is to be encoded is called the
“plaintext”
●
The encoded message is called the “ciphertext”
●
A “known-plaintext” attack is trying to break a
cipher given both the ciphertext and the plaintext

7. Breaking Ciphers I
●
How do we break the Caesar cipher?
●
All languages have a letter frequency. In English, the
most common letters are
e : 12.7%
t : 9.1%
a : 8.2% (from a sample of 100,000 characters)
●
Caesar cipher doesn't muddle letters so most
common letter will be 'e'. Given this we know the
offset and have broken the cipher

8. Breaking Ciphers II
●
What if the most common letter in the message was
's' not 'e'?
●
We'll be able to see that the “decoded” message is
garbage and try the next most common letter from
our list instead of e.
●
More sophisticated versions of this use many
statistical properties to try and identify valid
plaintext.

9. A (slightly) better Cipher
●
The XOR cipher is still used. It only provides very
weak security.
●
XOR is an operation on bits (like AND, OR etc.)
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 0
●
Note that a | a = 0 and a | b | b = a

10. XOR – an aside
●
The XOR cipher is just a form of a cipher invented
by Blaise de Vigenere (a French diplomat b. 1523)
●
This is know as a poly-alphabetic cipher.
●
It is not vulnerable to basic frequency analysis since
any given letter does not encode to the same letter all
the time.

11. XOR II – the algorithm
●
Choose a keyword
●
XOR the plaintext (split in groups of a suitable
length) with the keyword. This gives the ciphertext
●
To reverse, just XOR again with the keyword (a | b |
b = a)

12. Breaking XOR
●
XOR is easy to break
–XOR the ciphertext against itself shifted by various
amounts. If the shift is a multiple of the key length, ~6%
of the characters will be equal, if not ~0.4% will be equal
The smallest displacement that gives this affect is the
length of the key
●
(these numbers are for English ASCII text – they
must be determined in advance and will vary for
different types of plaintext)
(6% for two English texts. Low numbers for randomly matched texts. When shift is multiple of key length statistical
props of original text preserved. Encode two different texts with same key and calc number of equal chars – will be ~6%
and XOR doesn't destroy all statistical props of text. Assumes that key length is short compared to plaintext length)

13. Breaking XOR II
●
Now we know how long the key is.
●
Shift the ciphertext by the key length and XOR with
itself. Since a | b | b = a, this removes the key and
leaves us with the plaintext XOR'd with a copy of
itself shifted by the key length.
●
Now have k mono-alphabetic substitution ciphers so
do frequency analysis on each one in turn.
●
Each of these gives us one part of the key. Add them
together and we are done.

14. XOR III
●
XOR with a 160-bit key is used in the US to
“encrypt” digital mobile phones. This was what the
NSA allowed.
●
The method of breaking XOR/Vigenere ciphers
requires the plaintext to be much longer than the key
●
.....what happens if it's as long as the plaintext?

15. An Unbreakable Cipher
●
There is only one provably un-breakable cipher –
One Time Pads. Invented in 1917
●
This is the same as a XOR cipher with a key longer
than the message. The key must be truly random and
must not be re-used for another message.
●
Since the key is as long as the message, all
ciphertexts are equally likely so there is no way to
decode the message.
●
Used by the military for very secure, low-bandwidth
comms. Not practical for anything else.

16. How strong is my cipher?
●
A cipher with an infinite key length is secure, but
how many bits are needed (assuming the algorithm
has no other weaknesses)
●
XOR – strength is number of combinations of keys
2^k (but algorithm is flawed)
●
This is true of a general cipher with a binary key
since number of combinations is 2^k for a k-bit key.

17. How Strong is my Cipher II
●
All numerical estimates assume that the algorithm
has no weaknesses. This can never be proved –
always use public, well-known algorithms
●
The implementation must be correct
e.g. DiskLock for the MacIntosh (v2.1)

18. Big numbers
●
Remember that 2^23 requires twice as much time to
break as 2^22. 2^25 requires eight times as much
etc.
●
Some large numbers
–Age of the planet : 2^30 years
–Age of the universe : 2^34 years
–Number of atoms in the planet : 2^170
–Number of atoms in the sun : 2^190
–Number of atoms in the galaxy : 2^223

19. Real Symmetric Ciphers
●
There are several algorithms in common use
–DES. US government standard. Limited to 56 bits for
export.
–Triple DES. 56 bit DES run three times with three
different keys. Only a 112-bit key (effectivily) not a 168
bit key due to properties of the algorithms
–AES. The US government's new standard. Allows keys of
129, 192 or 256 bits)

20. Public-Key Cryptography
●
All the cyphers seen so far require a key to be
exchanged in advance
●
This was thought to be necessary until Duffie and
Hellman described public-key crypto in 1976
●
Idea is to use two keys – one secret, one public
●
The public one is used for encryption and is made
easily available but decryption requires the secret
key, which is kept secret.

21. How does it work?
●
The public and private keys are related to each other
via some mathematical function that is easy to
calculate but very hard to reverse.
–e.g. The RSA algorithm uses the problem of factorising a
large integer. Calculating a large integer is easy (just
multiply two large primes), but factoring the resulting
integer is very hard.
●
The plaintext and the public key are combined in
such a way that only the private key can recover the
plaintext

22. How big a prime is big?
●
RSA usually uses public-keys that are 1024 bits
long.
●
This is computationally equivalent to a 128 bit
symmetric key (remember that we don't have to
enumerate the whole space for a RSA key, only
factor the number)
●
Can use 2048 bit public-keys. This is very, very
large, but Schneier thinks that governments may be
able to break such a code by 2005

23. Uses of Public-key crypto
●
Websites (https://) are protected using public-key
cryptography.
●
User A contacts www.bank.co.uk
●
bank.co.uk responds with its public key
●
A uses this key to encrypt all his network traffic so
that the size of their overdraft remains secret
●
Only www.bank.co.uk can decrypt A's messages
since only it has the relevant private key.

24. But.....how does the bank respond?
●
In practice, the first message A sends to bank.com is
a randomly generated secret for normal symmetric
encryption
●
Both A and bank.com know this secret so can use
any agreed algorithm to encrypt their
communications
●
No-one else can find the secret since the
transmission of the secret was protect by public-key
crypto.

25. Digital Signatures
●
How do I prove who I am? Paper-based methods
(signatures, passports etc.) cannot be used online
●
Any stream of bits can be captured and replayed so
any “signature” must be different for each message
that we “sign” (including time!)
●
More generally, in the previous example, how does
A know that bank.com really is bank.com and not a
fake website?

26. Digital Signatures II
●
We use a property of RSA. The private and public
keys are interchangable in one sense:
–The private key can be used to decrypt messages
encrypted with the public key but also,
–The public key can be used to decrypt messages
encrypted with the public key
●
To solve the time problem, we append a time-stamp
to every message.

27. Digital Signatures III
●
I sign a document by encrypting it with my private
key.
●
To verify the signature, Jo Bloggs gets my public
key and uses that to decrypt the message.
●
Since only I have my private key (I hope!), Jo can be
sure that the message came from me.
●
Steps can be combined – I could encrypt a message
with my private key and then Jo's public key to send
an encrypted, signed message.

28. Message digests
●
In practice, public-key crypto is very slow, so rather
than signing the whole message we “digest” it
●
A digest is a one-way mathematical function that
gives different answers for different input
●
We apply the digest to the original message and then
sign the resulting digest. This is much quicker.

29. Problems – I
●
Key-distribution. A must get Bob's public key to
send him a message. How do I know that his key is
really his?
–Bob could digitally sign it. But our algorithm means that I
have to know Bob's public key to verify his signature!
–I get someone else (who I trust) to sign it and only use a
signature for which this is true. This is the most common
solution (VeriSign's whole business model is this), but re-
create some of the problems public-key crypto solved by
needing some pre-shared secrets or information.

30. Problems II
●
Even if the cryptography is perfect.....
–Computers can be taken over in other ways (viruses)
–Plaintext can be left in memory or in swap even after it
has been encrypted
–People are trusting. Just ask them for their password
–If all else fails, bribe someone or use sex (US Embassy,
Romeo agents)

31. ....and finally
●
Many other varients possible including digital
money (secure, non-tracable e-cash), zero-
knowledge proofs and digital voting
●
Always remember to use standard algorthms, but
that the crypto is probably not the weak point in the
system

32. References
●
In increasing order of technicality
–“Secrets & Lies”, B. Schneier, Wiley 2000. ISBN 0-471-
25311-1
–“The Code Book”. S. Singh, 4
th
Estate 1999. ISBN 1-
85702-879-1
–“Applied Cryptography”. B.Schneier, Wiley 1996. ISBN
0-471-11709-9