| Contents | Announcements | Exams | Literature | Videos and slides | Course notes and exercise sheets | Old exams |
Tanja Lange
Coding Theory and
Cryptology
Eindhoven Institute for the Protection
of Systems and Information
Department of Mathematics and Computer Science
Room MF 6.103
Technische Universiteit Eindhoven
P.O. Box 513
5600 MB Eindhoven
Netherlands
Phone: +31 (0) 40 247 4764
The easiest ways to reach me wherever I am:
e-mail:tanja@hyperelliptic.org
This page belongs to course 2WF80 - Introduction to cryptology. This course is offered at TU/e as part of the bachelor's elective package Security.
Contents
Classical systems (Caesar cipher, Vigenère, Playfair, rotor machines), shift register sequences, DES, RC4, RSA, Diffie-Hellman key exchange, cryptanalysis by using statistics, factorization, attacks on WEP (aircrack).
Some words up front: Crypto is an exciting area of research. Learning
crypto makes you more aware of the limitations of security and privacy
which might make you feel less secure but that's just a more
accurate impression of reality and it a good step to improve your
security.
Here is a nice link collection
of software to help you stay secure
https://prism-break.org/en/
and private
https://www.privacytools.io/.
If you study mathematics, you should have participated in "2WF50 - Algebra"
and "2WF70 - Algorithmic algebra and number theory".
If you study computer science or any other program you should have
participated in "2DBI00 - Linear Algebra and Applications",
"2IT50 or 2IT80 - Discrete structures", and
"2WF90 - Algebra
for security" before taking this course.
If not you can find some material in the Literature section
but note that you are on your own for learning this.
Lectures take place Mon block 3 and 4 in AUD 5 (except for Nov 13
Jan 16 where it is
in Flux 1.02)
and Thu block 7 and 8 in AUD 2 (except for Nov 23 when it is in
AUD 7).
We have two locations for the instruction sessions (Thu block 5 and 6),
namely Luna 1.240, and Altas 4.215 (except for Nov 16 when it is Atlas -1.820);
please join the room that's emptier. These rooms are still subject to change.
In 2020 and 2021 the course has been
running online with short videos – one video per topic,
so several videos per unit.
This year the course will be streamed and recorded.
This means that you do not need to attend the in-person
lectures if you're concernd about your health. Please stay home and
participate remotely if you are sick.
The teaching assistants for this course are:
It is not necessary to purchase a book to follow the course.
For some background on algebra see
For easy prototyping of crypto implementations I like the computer
algebra system Sage. It is based on
python and you can use it online or install it on your computer (in a
virtual box in case you're running windows).
I recorded a
video to
demonstrate how to use Sage https://www.sagemath.org/, covering basics of finite fields and
elliptic curves. The latter do not for this course so watch start till
minute 10:50 and then again for about 2 minutes after 19:30.
I also wrote a short ``cheat sheet'' with commands for Sage,
see here
For encrypting your homeworks you should use GPG/PGP. If you're
running Linux then GnuPG is easy to install.
GPG4win; if
you're using MAC-OS you can use GPG
Suite (though I'm getting reports that they changed their system and now
charge for the full version.
We are OK with having only the attachment being
encrypted and signed, but prefer proper encryption of the whole email.
Thunderbird has good integration and I hear that also outlook can
work well with the plugins.
30% of the grade is determined by homeworks. There will be six
sets of homework during the quarter. You should hand in your homework
in groups of 3 or 4. To make sure that you get used to crypto we require
solutions to be sent encrypted and signed with GPG/PGP. Each participant must
have communicated with the TAs at least once using GPG/PGP.
You can find the keys for the TAs linked above or also on the key servers.
If for some reason you need to email me,
you can find my public key for tanja@hyperelliptic.org on the key servers
and on my
homepage.
The exam will take place on 22 January 2024, 13:30 - 16:30; the rooms are
in S3 (Fontys) where we have kantine vak A, B, C and studie vak A, B.
This is information last checked on 21 Jan, please double check on the offical
TU/e pages before going to the exam.
The retake is scheduled for April 8, 18:00 - 21:00, the room is Atlas -1.715.
The exam
accounts for the remaining 70% of the grade.
For 2023 the lectures will be recorded and streamed.
In 2022, the in-person lectures were recorded and posted at
videocollege.tue.nl.
For the 2020 and 2021 editions of the course I recorded a lot of short videos
which you can find on the YouTube Channel.
The
course page for 2021 has short descriptions of all videos, slides,
and no-cookie links to the YouTube videos. Watch them
from there if you're on a low-cookie diet.
For even fewer cookies, you can find the
surfdrive. File names match the file names of the slides.
This section is extended through the course with notes of what happened in class and links to blackboard pictures. You can also find here the exercise sheets for the sessions on Thursdays.
13 Nov 2023
This is our first day of lectures. More to come here after the lecture.
The frist lecture was be given by
Monika Trimoska.
Monika presented the requirements that cryptography should achieve, namely to provide
confidentiality, integrity, and authenticity, against attackers that have
access to all messages sent and who may attempt to inject messages or to modify
messages. Then, presented an introduction to public-key cryptography and
signatures and ended with security notions.
These three sets of slides:
16 Nov 2023
Note that we have excerises in block 5 &6, lectures in block 7 & 8.
Here is the exercise sheet for block 5 and 6: exercise-1.pdf. See also the raw data if paste fails.
This year exercise 1 and 2 are combined and 3 is omitted.
If you get stuck on the Hill cipher watch the 2021 video on XGCD under
Math
background on the 2021 course page.
For most of the exercises the solution is obvious when you have it. If you're not sure, please ask the TA in your room to check you solution. There are many more pages on the web with tools for cryptanalysis of classical ciphers, e.g. https://www.guballa.de/vigenere-solver, https://www.braingle.com/brainteasers/codes/index.php, http://www.cryptool-online.org, http://practicalcryptography.com/ciphers/, https://www.boxentriq.com/code-breaking.
The first homework is due on 23 November 2023 at 13:30. Here is the first homework sheet.
For submitting your homework you need to
generate a keypair (a private and a public key). As the names suggest you
should keep the private key private and can publish your public key. The latter
is needed to encrypt messages to you and to verify signatures made by you, so
that's what you need to send in along with your homework solution and that's
also what your team mates need from you in order to communicate securely with
you. You can find the keys of the TAs above under Announcements.
Please remember to submit your homework by encrypted, signed email to
all the TAs.
Don't forget to include your public key and those of your team mates.
This second lecture was be given by
Monika Trimoska.
Monika covered Caesar cipher (original and a keyed version),
substitutionnn ciphers, the one-time pad, and Viginère cipher as well as
how to break them and how big the keyspace is.
Here are the slides
she used
She then covered column transposition as another historical cipher. The Playfair and
Hill ciphers were covered in the instruction session, see the exercise sheet.
These are the slides.
We had some rotor machines from the
Cryptomuseum
on show in the MetaForum. Currently we have Benne de Weger's Hagelin on display
(near the elevator on floor 6 of the MetaForum)
Check out the extensive website of the Cryptomuseum on crypto machines and spy craft.
As a second topic Monika covered stream ciphers as an example of symmetric-key
encryption and as a more practical alternative to one-time pads. All security
concerns of one-time pads apply – never use them twice – and additionally
stream ciphers need to be checked whether they really produce random-looking
outputs. Basic essentials to avoid the two-time pad issue is to use an IV
(initialization vector) to make sure that the stream cipher has a fresh
randomized starting point for each message and that the space for the IV is big
enough to avoid repetitions.
The slides are
here
20 Nov 2023
We covered feedback-shift registers (FSRs),
LFSRs and how to represent them via matrices.
(L)FSRs are examples of stream ciphers. The IV is used as the initial state and
the key defines the feedback function. Note that this is very much simplifying
things and LFSRs alone are really bad stream ciphers as you can recover the
state update from the IV and just n more ooutput bits. However, LFSRs are used
in bigger constructions because we can reason well about the periods they
geerate (without having to try everything).
We have seen that depending on the
function the output sequence can have a very short period. For LFSRs we have
established that the output sequence is periodic (not just ultimately periodic)
if c0=1 and that the period divides the order of the state-update materix.
We also established that the all-zero state leads to the all-zero
sequence of period 1 for any LFSR. We covered 2 complete examples for LFSRs with
state-size 3 for and all states, one had periods 7 and 1, the other had
4,2,1,1. Note that there are 2^n different states, so the sum needs to match
2^n, so 8 in thess examples.
Finally we showed that the characteristic polynomail of the state update matrix
is x^n -cn-1xn-1
-cn-2x
Pictures of black boards are here.
If you are following the course remotely note that this lecture corresponds to the videos for 16 Nov 2020.
23 Nov 2023
Here is the exercise sheet for block 5 and 6: exercise-2.pdf. You should really try to
solve these exercises and make some conjectures about how orders,
degrees, and periods fit together.
You can call over the TAs for checking and I've put a quizz on Canvas
so that you can check the numbers yourself -- and ask the TAs if you didn't get
the right answer. I do expect that you use a computer for the larger examples.
In class we covered more details on LFSRs, in particular we took some of the conjectures on orders of C and f(x) that you should have found in the exercise session, turned them into theorems, and proved them. Now that they are proven, you can use them as facts, so proofs are useful. I used Rabin's irreducibility test, you should know that from previous lectures and you should be able to recognize some irreducible polynomials of small degree namely x, x+1, x^2+x+1, x^3+x+1, and x^3+x^2+1 as factors of polynomials.
As a seccond topic we covered sums of LFSRs. On the practical side is this can be motivated by asking what we can build from given small hardware components, and in fact many designs are actually build from such pieces, but it is also a useful step in. our quest to understand LFSRs which do not have irreducible LFSRs and we got some ideas – and disproved some. See here for the slides that I showed of the sums.
Pictures of black boards are here.
The second homework is due on 30 November 2023 at 13:30. Here is the second homework sheet. Please remember to submit your homework by encrypted, signed email to the TAs. Don't forget to include your public key and those of your team mates.
27 Nov 2023
At the end of the previous lecture we had found a counterexample to our
hypotheses of what happens when we add two LFSRs. The main result of this
lecture is that the characteristic polynomial of the LFSR that one obtains as
the sum of two LFSRs equals the lcm of the characteristic polynomials of the
LFSRs that are added up. We also proved that for an irreducible characteristic
polynomial all non-zero output sequences have the same period length. Both of
these results needed generating functions, which are very useful tools to know
anyways. I got stuck in getting the indies right – next year I'll use a
cheat sheet.
For a clean version see the 'Math vs. Mystery' video (maybe with pauses and rewiding) and checking the slides. However, do check the blackboard/live recording to see the instructions of how to approach the analysis of LFSRs.
Further reading on finite fields and the mathematical theory of LFSRs is in Lidl/Niederreiter (see literature section), van Tilborg (see literature section), and David Kohel's lecture notes.
Pictures of black boards are here.
30 Nov 2023
Here is the exercise sheet for block 5 and 6: exercise-3.pdf.
The third homework is due on 07 December 2023 at 13:30. Here is the third homework sheet.
Please remember to submit your homework by encrypted, signed email to
all the TAs (and not to Tanja).
Don't forget to include your public key and those of your team mates.
Do not submit as a singleton or pair, the minimum group size is 3.
LFSRs are used in practice because they are small and efficient, but they
need a non-linear component to be secure. I covered three ciphers from
telecommunication (A5/11, A5/2, and SNOW-3G) which all are based on LFSRs with
some nonlinear components. See the slides
for their definitions and some details.
These ciphers were in every cell phone using GSM 2G and downgrade
attacks were possible for a long time.
It sounds like the 54 bits were
a compromise between countries wanting strong crypto and others wanting
weak crypto. One of the first postings on it
with some details on the history
(note that the original link
does not work now)
an attack idea for A5/1 by Ross Anderson is from 1994, but many
details were missing. The full algorithm descriptions of A5/1 and its
purposefully weakened sibling A5/2 were reverse engineered and
posted in 1999 by
Marc Briceno, Ian Goldberg, and David Wagner. The same group also
showed a devastating attack on A5/2, allowing for real-time decryption.
Sadly enough, the A5 algorithms allow downgrade attacks, so this is a
problem for any phone which has code for it, which is most until
recently. Also A5/1 does not offer 2^54 security (54 bits is the
effective key length) but only 2^24 (with some precomputation/space).
However, A5/2 is broken even worse, in 2^16 computations, with efficient
code online, e.g A5/2 Hack Tool.
The cipher we analyzed in the exercise session is RC4. Even as recently as 2013
this was the preferred symmetric cipher for https. I find it quite
surprising that such a widely used cipher exhibits properties we can
find in an exercise session (well, knowing where to look, of course).
Note that
RC4 was a secret design, available only as black box implementation.
Soon after it was leaked as "arcfour" weaknesses were found.
I summarized some weaknesses on the board but for showing some of the biases I
used these slides.
A nice overview of lightweight ciphers, including more modern and less broken ones is given by Alex Biryukov and Leo Perrin.
Since making those slides in 2020 even more details on GSM have come out and in 2021 details of two more GSM ciphers, GEA-1 and GEA-2, were published and analyzed. I mentioned that I wanted to show some more, take a look at page 7 of the scientific publication about the attack. The attack made news in 2021 because many new cell phones were still supporting GEA-1, even though it was "removed" from the standard by ETSI in 2013, and because it was unusually weak: GEA-1 has a 64-bit key but it is designed such that after initialization there are only 2^40 different states (instead of 2^64 that should be possible). The design was not public, but a cursory look would not reveal this property; this strongly looks like a back door. GEA-2 does not have this problem (and so far is not discontinued) but it also offers far less security than it should. It is unclear whether the techniques used in the attack were known in the 1990s.
If this didn't make you sufficiently skeptical of everything ETSI, here is another one that came out this summer (2023) TETRA:BURST against the Terrestrial Trunked Radio (TETRA) standard, a standard by ETSI which is used for radio communication incl. for critical infrastructture and emergency servvices, and which totally crumbled under analysis.
Better stream ciphers exist, e.g. the final portfolio from the eSTREAM competition has held up well.
Pictures of black boards are here.
05 Dec 2023
Stream ciphers protect the confidentiality of messages but not the integrity.
An attacker flipping a ciphertext bits causes the same bit to flip in the
plaintext. Integrity protection is achieved using Message Authentication Codes
(MACs). MACs belong to symmetric-key crypto and veryifying a MAC tag takes the
same key as generating one. Hence the receiver is convinced of the authenticity
of a message but cannot convince a 3rd party of it. The latter is achieved by
signatures, which can be verified using a public key.
To build MACs we need the definition of cryptographic hash functions.
THese compress arbitrary-length messages to fixed-length messages. Hash
functions find use also outside crypto, e.g. to deduplicate data and as short
fingerptints, but we require more properties.
Cryptographic hash functions need to provide pre-image
resistance, second pre-image resistance, and collision resistance.
If
the output of the hash function has n bits then finding a collision
takes on average 2n/2 trials (use the birthday paradox to
see this) and finding a preimage or second preimage takes on average
2n trials.
MD4 is completely broken; for MD5 it's easy to find collisions and meaningful
ones are possible, see
MD5 considered harmful today: Creating a rogue CA certificate.
First SHA-1 collisions were computed in 2017
(see https://shattered.io/) followed by a
way to create meaningful SHA-1 collisions in
https://sha-mbles.github.io/.
SHA-2 (which includes SHA-256, SHA-384, and SHA-512 and SHA-3 (and the other
SHA-3 finalists) are likely to be OK.
We covered design of hash functions using the Merkle-Damgaard construction
and how this enables length-extension attacks on a simple MAC construction
unless special padding is used. On the bright side, the iterative design of the
function makes it eaiser to study it. H is collision resistant if C is, so
cryptanalysts can focus on C. Note that the IV is fixed in hash functions.
Pictures of black boards are here.
07 Dec 2023
Here is the exercise sheet for block 5 and 6: exercise-4.pdf.
The fourth homework is due on 14 December 2023 at 13:30. Here is the fourth homework sheet.
Please remember to submit your homework by encrypted, signed email to all TAs
(and not to Tanja).
Don't forget to include your public key and those of your team mates.
Do not submit as a singleton or pair, the minimum group size is 3.
After a short recap of the MD construction and length extension (as feature and attack vector) we finished discussing MACs. I showed HMAC as a design that protects against length-extension attacks even when an MD-based hash function is used.
The exercise session today covered DES as an example of a block cipher.
DES is a Feistel cipher.
I showed the general design and gave some description of how it is possible to
decrypt even though the functions f_i are not invertible. I showed the
schematics of the function for DES from page 4 of these slides
The S-box is the non-linear part; the NSA strengthened the S-boxes in
the original design (Lucifer) against differential attacks (but made the keys much shorter).
In the exercises we saw that small changes in
the input lead to big changes in the output.
56 bits for the key is not secure enough!
First brute force attack was done with "DES Cracker" for 250k USD.
In 2006 a team from Bochum and Kiel built
COPACOBANA
which can break DES in a week for 8980 EUR (plus some grad-student
time).
With only 56 bits in the key and atack takes 2^56 trial encryptions to find the
likely candidate key k given a pair (m, Enc_k(m)). 2DEWS has 112 bits in the
key but with a meet-in-the-middle attack can be broken in 2^57 computation and
2656 space.
Still in common use at banks is 3-DES, sometimes with k1=k3. Full 3-DES needs
2^112 steps to break, there are some more weaknesses in 2-key 3-DES (k1=k3).
Block ciphers can encrypt data in blocks of fixed length n. If you encrypt
each block separately your encryption is vulnerable to statistical attacks,
A
famous example of how weak this is is the ECB
penguin.
The name for this approach is ECB (electronic code book) mode.
The approach means that identical blocks encrypt the same way.
To encrypt messages longer than one block you need to use a mode of
operation.
More reasonable modes than ECB are CBC,OFB, and CTR. These modes
ensure that identical plaintext blocks do not lead to identical
ciphertext blocks.
Pictures of black boards are here.
11 Dec 2023
To conclude the symmetric-key part we covered multi-target attacks and
contrasted the settings between symmetric and public-key crypto incl. what
powers the attacker has.
I did a recap of the math concepts I expect you to know, incl. a more detailed presetnation on the Euler totient function and on exponentiation. For the latter I showed these slides. Try computing a^b mod n on your pocket calculator to get immediate feedback on what I mean or see your computer running out of memory when computing m^d for large b.
After setting up public key crypto for public-key encryption and signatures, we covered schoolbook RSA encryption and why it works. We also covered one pitfall of schoolbook RSA which happens because of too small exponents and lack of padding. We'll see more attacks in this scenario on Thursday (exercise and lecture). This is a good moment to brush up some mathematics, we need Fermat's little theorem, XGCD, and the Chinese Remainder theorem.
Pictures of black boards are here.
14 Dec 2023
Here is the exercise sheet for block 5 and 6: exercise-5.pdf.
The fifth homework is due on 21 December 2023 at 13:30. Here is the homework sheet. Please remember to submit your homework by encrypted, signed email to all TAs. Don't forget to include your public keys. There is no instruction or lecture on 21 December, but the homework deadline goes through as normal and we will post a sheet of exercises for your entertainmaint.
We covered RSA signatures and that RSA is atypical in that decryption
matches signing and encyprion matches verification. Normally such operations
are very different (apart from the general data flow that the former need the
private key and the latter the public key).
We covered some more weaknesses of schoolbook RSA encryption:
RSA encryption is homomorphic; per se this
is not a problem (and can be a feature in some systems) but we showed that this
means that schoolbook RSA is not OW-CCA-II secure (see below).
The second weakness is if there are related messages, such as m_2=am_1 + b for
known a and b. The proof of the relation between the expressions A and B is on
these slides.
As a third weakness we showed that
if e receipients
all use public exponent e (and their own moduli n_i) then one can recover m^e
modulo the product of the moduli which is m^e as an integer (without
reduction) from which one can compute the integer e-th root with a normal
calculator. For a numerical example for e=3 see the last page of these
slides.
To understand how to get out of the problem of studying all kinds of attacks we looked into security notions. Security notions and attack definitions formalize what we consider an attack and what powers the attacker has.
For encryption the attacker may do a chosen-plaintext attack (CPA) or a chosen-ciphertext attack (CCA) (see Monday's lecture). There are two versions of CCA security: in CCA-I the attacker gets to request decryptions of arbitrary ciphertexts until he sees c; in CCA-II the attacker can request decryptions of ciphertexts c' (not equal to c) also after receiving c. We considered the latter.
For encryption the goal is to recover plaintext from ciphertext;, i.e. to break one-wayness. We typically request that a scheme is so strong that the attacker learns no information about the plaintext from the ciphertext; this is called semantic security. However, this is hard to deal with in practice. An equivalent and more practical security requirement is indistinguishability: the attacker chooses two messages m0 and m1 and is then presented with a ciphertext c which encrypts one of m0 and m1. The attacker wins if he correctly guesses which, i.e., if he can distinguish the ciphertexts. To deal with a 50% chance of guessing, the advantage of the attacker is defined as the extra chance on top of the 50%.
As said above, RSA is homomorphic, which defeats some security notions and can mean
real attacks (depending on the setting).
Schoolbook RSA is not is not OW CCA-II secure, because of the homomorphic
property: to decrypt c the attacker can ask for the decryption of
c'=c*2^e, obtain m' and get m = m'/2.
Because schoolbook RSA is deterministic, it is
not even iIND-CPA secure: the attacker can simply encrypt m0 and m1
himself and compare the results to c..
Pictures of black boards are here.
18 Dec 2023
For signatures, the attack goal is to forge signatures,
this could mean to generate any valid (m,s) pair (existential forgery)
or to generate valid (m,s) for a meaningful message m (universal
forgery).
Today we covered the Diffie–Hellman key exchange as interactive protocol
and as semi-static DH where one part uses a long-term public-key.
Eve can compute the shared secret if she can compute a from h_A or b from h_B.
There might other ways than computing these discrete logarithms but it is
important to choose the groups such that these attack are as hard as
possible.
The abilities of the attacker vary; for signatures it might be a key-only
attack (KOA), a known message attack (KMA), or a chosen message attack
(CMA). In the latter two cases the attacker sees valid signature pairs
(m,s); in CMA the attacker can choose for which messages he sees
signatures.
I didn't cover this, but to make RSA a randomized encryption one uses some padding; however
this is also error prone. PKCS#1 v1.5 is a negative example which is
broken using Bleichenbacher's attack. Take a look at https://robotattack.org/ for a
recent use of Bleichenbacher's attack in practice. You should be able
to understand details of the full paper Return Of Bleichenbacher's
Oracle Threat. RSA-OAEP is a better padding scheme.
You can find PKCS#1 v1.5 on the last page of these
slides
I showed the p-1 method and how and why it works and showed some numerical examples from these slides.
The second topic of today is the Diffie-Hellman key exchange.
After discussing some examples of bad groups and good groups (multiplicative
group of a finite field or group of points on an elliptic curve) we coverd a
generic attack, i.e., an attack that works for any group.
The Baby-Sep-Giant-Step (BSGS) algorithm is an algorithm to compute discrete
logarithms in a cyclic group
with generator g, i.e. given g and h_A =g^a it computes a.
Put m=floor(√l), where l is the order of g. For us that is p-1 for now.
BSGS computess all powers of the generator from g^0=1 up to g^(m-1),
these are the baby steps (incrementing by 1 in the exponent).
Then it computes S=g^(-m) and checks for each h_A * S^j for j = 0,...
whether it is in the list of baby steps; these are the giant steps
(moving by -m in the exponent). If a match happens, we have
g^i=h_A * S^j = g^a*g^(-mj), thus a=i+mj.
I showed a numerical example of BSGS from these
slides
Pictures of black boards are here.
21 Dec 2023
There are no lectures or instructions today.
You can do the 6th exercise sheet exercise-6.pdf
whenever you get around to it and verify your results with the quiz on Canvas.
The sixth (and last) homework is due on 11 January 2024 at 13:30. Here is the homework sheet. Please remember to submit your homework by encrypted, signed email to all TAs. Don't forget to include your public keys. This is your last chance if you still need to do an encrypted round of communication.
Enjoy your holidays. If you want to do some crypto take a look at the old exams (below). The exam for 2WF80 will be in person, on paper, without laptops, without books. so pick exams no more recent than Jan 2020 and the exams from 2023 for practicing in the same setting. The intermediate two years (2021 and 2022) had different conditions.
08 Jan 2024
Silvia Ritsch
was so nice to give this lecture.
Before the winter break we covered the Diffie – Hellman key exchange and
the discete logarithm problem. Today Silvia showed ElGamal encryption and
ElGamal signatures which both use the discrete logarithm.
ElGamal encryption requires the message m to be an element of the group, so
typically it is easier to use DH to generate a share secret and then symmetric
crypto to encrypt and authenticate the message. ElGamal encryption is
interesting if one wants homomorphic properties (see the earlier discussion
abour RSA being homomorphic and that that means that the scheme cannot be
OQ-CCA-II secure) as the product of two ciphertexts (taken component wise) is
an encryption of the product of the messages.
ElGamal encryption starts the same as the DH key exchange, with Alice
choosing a secret key a and computing and publishing public key h_a = g^a. Then
Bob, who wants to encrypt some message m to Alice, chooses a random k and computes r
= g^k. He also takes Alices public key and computes (h_a)^k. This is basically
the shared key from DH. He then encrypts the message by multiplying with this
key: c = m * (h_a)^k. Finally, he sends (r,c) to Alice. Alice can decrypt by
computing m = c / r^a.
ElGamal signatures are a little more involved. We will use l = ord(g). Alice again picks random a and computes and publishes h_a = g^a. To sign a message m, she picks a random k, computes r=g^k, and s=k^{-1}(H(m)-ar) mod l, where H is a cryptographic hash function. Every term in s is defined modulo l, except r, which is defined modulo p. Therefore the value that is send for r should be used exactly as is. The signature is then (r,s). It is accepted when g^{H(m)}-r^s(h_a)^r = 0. Anyone not knowing a cannot compute s. Note that computations in the exponent happen automatically modulo l, otherwise modulo p. Breaking the system is as hard as the DDH problem. ElGamal signatures serve as a basis for more modern signature systems such as DSA.
As a second topic, Siliva discussed the idea of secret sharing. In many cases the private key
should not be in posession of a single user. A nice analogy is a bank vault
which requires multiple keys to open it. The Shamir secret sharing scheme is a
t-out-of-N threshold system based on polynomials. The idea behind it is that it
requires t points to recover a (t-1)-degree polynomial. The sharer generates a
random polynomial of degree (t-1), such that f(0)=s. The values at x=1, x=2,
etc. are the shares received by the parties. The polynomial, or only the secret
value, can be reconstructed from sufficient shares by Lagrange interpolation.
t-1 or fewer users learn nothing about the secret (every possible value has the
same probability).
In practice nobody should ever know s. In theory a trusted party could compute
and use s, then forget it, and only share the result of the required
computation. A better solution is that users locally compute the desired output
with their shares, and only then combine their shares to reveal the result (but
not s). Also, often you want nobody to know the secret (which could be a secret
key), not even the sharer. This can be achieved by generating it in a
distributed manner: Everybody picks a random integer. The secret is then the
sum of all the integers. To compute it every user shares its integer in a
t-out-of-N manner (every user should receive the shares corresponding to the
same x-value), and then adds all the shares it received (including the share of
its own secret). This is basically adding the underlying random polynomials.
Silvia was so nice to take pictures of black boards, there
are here.
11 Jan 2024
Here is the exercise sheet for block 5 and 6: exercise-7.pdf.
I repeated the DDH problem and then showed a simple attack against it that
works if g generates the whole multiplicative group F_p^* and reuqires
computing the (p-1)/2-th power of g^a dn g^c to determine if a and/or c are
even. If a we also need to compute the parity of b the same way. We get the
parity by observing that g^((p-1)/2) = -1 and g^(p-1) = 1; the former holds for
all odd powers of g and the latter for all even powers. If c is chosesn
randomly then there is only a 50% chance that the parity of ab and c match
giving us a high chance of solving DDH. This problem can be avoided by choosing
p = 2p' + 1 and g of order (p-1)/2.
I then repeated ElGamal encryption and that m has to be in the group generated
by g (so we cannot win at IND-CPA by picking m_0 = 0). With this, ElGamal is
IND-CPA secure if DDH is hard because g^a, g^r and c/m_0 is a valid DH triple
with last entry g^(ar) if m_0 was chosen and g^(ar) m_1/m_0. This gives us
exactly the DDHP.
Similar attacks would work for
checking cubes, 5th powers, 7th powers etc. which motivates working in a prime
order subgroup. Note that then the DDHP is adjusted to having h picked as
g^{ab} or as g^c for random c so that one does not trivially break it by
noticing that h is not in the right subgroup.
Note also that ElGamal encryption is homomorpihis (see notes from 8 Jan) and
thus not CCA-II secure. For these reasons and the inconvenience of mapping to
the group generated by g we use DH + symmetric encryption instead. Note that
for the shared key we what to hash more things into the key k =
hash(g^(ab),g^b, g^b).
This is an example of a KEM. we covered the general concept of the KEM/DEM
paradigm and how to turn RSA ia KEM by encrypting a random message. This nicely
avoids all attacks using that m is human readable or tnat it can have some
algebraic structure.
For an interesting case of use for ElGmal encryption see this research by Pierrick Gaudry here on the Moscow electronic voting system which didn't ensure that all messages were squares while g generated the subgroup of squares. This meant that an attacker can distinguish whether a vote was for a candidate for whom the corresponding m is a square or not by computing (h_A^rm)^((p-1)/2). SImilar to what we covered before in the DDH attach this gives 1 if m is a square (and thus in the subgroup generated by g) and -1 otherwise.
Finally I covered how an active attacker can mount a man-in-the-middle attack by ipersonating Bob to Alice and Alice to Bob while in fact doing separate key exxchanges with them. This can be avoided by Alice signing her g^a and Bob signing his g^b. We'll cover more on this on Monday.
Pictures of black boards are here.
Thanks to the student who took them for me.
15 Jan 2024
Any system based on DLP has at most
square root of the group order hardness of the DLP.
For elliptic-curve groups that's also the best known attack complexity
while index calculus is a faster attack on finite-field DLP which reduce the
security per bit to that of RSA numbers, so fields have 2048 - 4096 bits.
The element g is always taken to generate a prime-order subgroup. Choices are that p=
2p'+1 for p' a prime as well and then g generating the subgroup of squares or
that g generates a much smaller (256 bits) subgroup.
In the previous lecture we covered how Eve can mount a man-in-the-middle attack on unauthententicated DH. In this lecture we discussed how to avoid this attack using signatures or 3-DH with long-term keys and epehemeral keys. We also covered the Needham-Schroeder protocol as an important example of how not to achieve authenticity by showing how Eve can impersonate Alice to Bob if she can get Alice to start a conversation with her. The reason that this works is that Bob's reply is not linked to the scope of his exchange with Eve and Eva can pass it on to Alice as her own message in the conversation Alice–Eve.. It's easy to fix this by including the public keys of all communicating parties in the encrypted message or include the hash of the transcript in the encrypted message (if space is an issue).
Finally we covered some unusual types of signatures.
Blind signatures are used in eCash and easy to get from homomorphic
RSA signatures. I showed how the scheme works and also commented on what to
watch out for, in particular double spending.
Undeniable (I used the wrong term on the blackboard)
signatures limit who can verify a signature and
require interaction between the signer and the verifier to verify. I showed
Chaum's protocol which uses the DLP for 'signatures' and how an interactive
protocol shows that the signature is valid – and how Alice can show that
she did in fact not sign a message. For a numerical example see the
last two pages from these slides.
Pictures of black boards are here.
18 Jan 2024
Both the instruction and the lecture were Q&A sessions. For the
instructions please prepare and ask about the exam from April 2023: here.
For the lecture slot you can ask
me anything incl old exams. Most relevant are the last two exams and
the exams of Jan 2020 and eaerlier, i.e., in
the handwritten format which matches what you'll encounter on the 22nd.
It's best if you come prepared with questions or even email me them before; I
will talk about them in the order in which I got them.
You can see the questions on the pictures below.
For LFSRs I covered more pieces than any single exam has in order to cover the
spread. I tried to document if an exercise corresponds to an old exam, the last
lecture in Jan 2023, or is just some random example I made up now.
Pictures of black boards are here.
22 Jan 2024
Exam! See above for room info and please check online
before the exam, there might be some changes.
This course was given for the first time in Q2 of 2014. Here are my exams so far
