Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

ISE > CRY > Flashcards

CRY Flashcards

1
Q

cryptography and cryptanalysis

A
  • Cryptography is the science and study of secret writing
  • Cryptoanalysis is the science and study of methods of breaking ciphers

Today:

  • cryptography is the study of mathematical techniques related to aspects of information security, such as confidentiality, data integrity, entity authentication, and data origin authentication

Cryptography does not solve security problems; it just transforms them into other problems, which are hopefully easier to handle.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Law enforcement Key recovery Key escrow

A
  • In many countries laws regulate how a law enforcement agency (LEA) can intercept traffic.
  • Key recovery makes cryptographic keys available to their owner.
  • Key escrow makes keys available to a LEA
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

cryptographic security

A

Cryptographic Security

  • Unconditional Security
  • Conditional Security
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Unconditional Security

A
  • Unconditional Security: System is secure even if adversary has unbounded computing power.

→ Security can be measured using information theory

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Conditional Security

A
  • Conditional Security: System can be broken in principle, but this requires more computing power than a realistic adversary would have.

→ Security can be measured using complexity theory

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Cryptographic security services

A
  • Data confidentiality: encryption hides the content of messages → only authorized users get the content
  • Data integrity: integrity check functions (hash functions) detect changes to data → verify that data is correct & complete, or detect that this is not the case
  • DOA: digital signatures and message MACs verify the source and integrity of data → verify that data is original and comes from a specific source, or detect that this is not the case
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

cryptographic hash functions

A
  • often used for integrity checks
  • apply hash function h to a document x and store the result h(x) in a secure place
  • result h(x) is called “hash value”, “message digest” or “checksum”
  • changes to x can be detected by re-computing the hash of x and comparing the result with the stored value
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Definition hash function

A

hash function is a function h which has, as a minimum, following two properties

  • Ease of computation: Given h and an input x, it is easy to compute h(x)
  • Compression: the hash function maps inputs of arbitrary length to fixed length results

Note: hash function usually implies an unkeyed hash function.

a keyed hash function is a function h(x,k) that takes some arbitrary-length input x and a fixed-length key k as input

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Manipulation detection codes (MDCs)

A

Used to detect changes to a document; unkeyed hash

Two types of MDCs:

  • One-way hash function (OWHF): finding an input which hashes to a pre-specified hash-value is difficult
  • Collision resistant hash function (CRHF): finding any two inputs having the same hash value is difficult
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Message authentication codes (MACs)

A

Used to assure both the source of a message and its integrity; keyed hash function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Security properties of hash functions (see HAC)

A
  • Pre-image resistance (one-way): for any given y, it is computationally infeasible to find x so that h(x)=y
  • 2nd pre-image resistance: given x, it is computationally infeasible to find x’, x ≠ x’, so that h(x)=h(x’)
  • Collision resistance: it is computationally infeasible to find x and x’, x ≠ x’, so that h(x)=h(x’)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Properties of one-way functions

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Hash functions

A

OWHF:

  • ease-of-computation, compression,
    pre-image resistance, 2nd-preimage resistance
  • One-way functions can e.g. be used for storing passwords

CRHF:

  • ease-of-computation, compression, 2nd-preimage resistance, collision resistance
  1. Collision resistance implies 2nd-preimage resistance
  2. In practice, CRHF usually are preimage resistant as well
  3. Some pathological examples are collision resistant but not preimage resistant

Well known hash functions: SHA-1, RIPEMD-160, MD5

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Properties of cryptographic hash functions

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Checksums

A

The result of applying a hash function is called hash value, message digest, or checksum.

The last term creates frequent confusion:

  • In communications, checksums often refer to error correcting codes, typically a cyclic redundancy check (CRC).
  • Checksums used by anti-virus products, on the other hand, must not be computed with a CRC but with a cryptographic hash function.

Note: A cyclic redundancy check (CRC) is not a cryptographic hash function: CRC’s are designed for detecting transmission errors

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Some use cases of crytographic hashes (OWHF, CRHF)

A

CRHF:

  • Verification of data integrity, signatures
  • File identification (P2P, git)

OWHF:

  • Password Storage
  • Key derivation
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Birthday paradox

A
  • Given an n-bit hash y, the expected number of tries before an x with h(x)=y is found is 2n.
  • Given n-bit hash values, a set of 2n/2 inputs is likely to contain a pair causing a collision
  • Birthday paradox: put m balls numbered 1 to m into an urn; draw a ball, list its number, and put it back; repeat; for m → ∞, the expected number of draws before a previously drawn number appears is

√0.5*π*m

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Complexity of brute-force attacks

A

Output size of hash function: n bit Pre-image and 2nd pre-image:

  • Average complexity: O(2n)

Collision: birthday „attack“:

  • Average complexity: O(20.5n)

Illustration of complexity:

1 Gops/s, 100 parallel ops/unit, 1000 units:

264 ops in about 50 hours
280 ops in about 380 years
2128 ops in about 1017 years

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Construction Hash function

A

Pattern for the design of fast hash functions:

  • The core of the hash function is a compression function f that works on fixed size input blocks.
  • An input x of arbitrary length is broken up into blocks x1,…, xm of the given block size; the last block has to be padded.
  • Compute the hash of x by repeatedly applying the compression function: with a (fixed) initial value h0, compute hi = f(xi||hi-1) for i=1,…, m and take hm as the hash value of x.

The symbol “||” denotes concatenation.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Hash Functions: A Typical Architecture

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Hash function constructions examples

A

Current generation: SHA-512

  • Whirlpool, …
    SHA-3 (Keccak)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What if input data is not a multiple of compress function input data size n?

A

Trivial padding: add as many 0-bit as necessary to obtain a multiple of n (Example: n=64)

  • „0x45“ => „0x4500000000000000“
  • „0x4500“ => „0x4500000000000000“
  • Result: H(„0x45“) = H(„0x4500“)

Improved padding: add 1 single 1-bit and, after that, as many 0-bit as necessary to obtain a multiple of n

  • „0x45“ => „0x4580000000000000“ „0x4500“ => „0x4500800000000000“ Result: H(„0x45“) ≠ H(„0x4500“)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

MD-Strengthening:

A

MD-Strengthening:

  • Add as many 0-bit as necessary to obtain a multiple of n
  • Add another block that encodes the full message length
  • Avoids simple 2nd preimage attack

Some additional benefits

  • Avoids long message attacks
    Avoids fixed-point attacks
    Avoids trivial collisions for free choice of IV
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Input Message Size: Padding

A

Padding as defined for MD5, SHA-1, SHA-224, SHA-256

  • Add a single 1-bit, then as many 0-bit as necessary to obtain input size congruent 448 (mod 512)
  • Add a 64-bit word indicating total input data size (mod 264)

SHA-384/SHA-512:

  • Same idea, but 1024 bit blocks and 128 bit for length
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Message Authentication Codes

A

Cryptographic Hash:

  • Do not depend on any secret key
  • I.e., anyone key calculate the hash
  • For integrity checks, hash values have to be protected!

Message Authentication Code (MAC)

  • Similar to cryptographic hash
  • But: dependent on a secret key
  • Knowledge of key necessary for calculating (or verifying) the message authentication code
  • keyed hash function for data origin authentication
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Message authentication codes (2)

A

Simple constructions:

  • “secret prefix”: calculate h(k || m)
  • “secret suffix”: calculate h(m || k)
  • “secret envelope”: calculate h(k1 || m || k2)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Message authentication codes (3)

A

HMAC construction: take a hash function h, for a key k and a document x, compute

HMAC(x) = h(k × o_pad || h(k × i_pad || x))

(i_pad, o_pad are padding fields, “||“ means concatentation)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Encryption

A

Encryption algorithms (ciphers) protect the confidentiality of data

Some encryption algorithms can also be used for integrity checks

A plaintext (clear text) x is converted into a ciphertext under the control of a key K

  • we write eK(x)

Decryption with an appropriate key computes the plaintext from the ciphertext

  • we write dK(x)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Symmetric key encryption

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Symmetric key encription

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Cryptoanalysis

A

Cryptanalysis: science of recovering the plaintext from ciphertext without the key.

Always assume attackers know the algorithms used

  • Algorithms can be published to facilitate the evaluation of their security
  • Security should depend on secrecy of the key, not the algorithm

Contrast with security by obscurity.

  • Analogy: Hide a letter under your mattress versus lock it in a safe, whose design has been published and whose locking mechanism has withstood attacks from the world’s best safecrackers.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Defining Security with Games

A

Games are frequently used to model formal security properties!

  • Cryptosystem is considered secure if no adversary can win the game with significantly greater probability than an adversary who just guesses randomly
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Model of Attack

A

We can think of the adversary as playing a game:

  • Input: Whatever adversary necessarily knows from the beginning, e.g., public key, distribution of plain texts, etc.
  • Oracle: Models information adversary can obtain during an attack. Different kinds of information characterise different types of attacks.
  • Output: Whatever the adversary wants to compute, e.g., secret key, partial information on plain text, etc. He wins if he succeeds.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Attacks

A
  1. Cyphertext Attack
    Given: eK(x1), eK(x2) …

Goal: deduce x1, x2 ,…, or K

  1. Known Plaintext Attack
    Given: (x1, eK(x1)), x2, eK(x2)), … Goal: deduce K
  2. Chosen Plaintext Attack
    like 2, but the attacker can choose xi
  3. Adaptive Chosen Plaintext Attack
    can not only choose plaintext, but can modify the plaintext based on encryption results
  4. Chosen ciphertext
    Attacker can chose different ciphertexts to be decrypted and gets access to the decrypted plaintext.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Attacks

A
  1. Cyphertext Attack
    Given: eK(x1), eK(x2) …

Goal: deduce x1, x2 ,…, or K

  1. Known Plaintext Attack
    Given: (x1, eK(x1)), x2, eK(x2)), … Goal: deduce K
  2. Chosen Plaintext Attack
    like 2, but the attacker can choose xi
  3. Adaptive Chosen Plaintext Attack
    can not only choose plaintext, but can modify the plaintext based on encryption results
  4. Chosen ciphertext
    Attacker can chose different ciphertexts to be decrypted and gets access to the decrypted plaintext.
35
Q

Cryptographic Security

A
  1. Specify an oracle (a type of attack).
  2. Define what the adversary needs to do to win the game, i.e., a condition on his output.
  3. The system is secure under this definition, if any efficient adversary wins the game with only negligible probability.
35
Q

Cryptographic Security

A
  1. Specify an oracle (a type of attack).
  2. Define what the adversary needs to do to win the game, i.e., a condition on his output.
  3. The system is secure under this definition, if any efficient adversary wins the game with only negligible probability.
36
Q

Symmetric Key Cryptography

A

An encryption scheme({eK1 :K1 ∈K},{dK2 :K2 ∈K})is symmetric if for each pair (eK1, dK2) it is computationally “easy” to determine dK2 knowing only eK1 (and vice versa).

In practice: eK<sub>1</sub> = dK<sub>2</sub>
Symmetric ciphers (secret key cryptography): same key is used for encryption & decryption
  • Encryption protects e.g. documents on the way from A to B
  • A and B have to share a key and keep their keys secret
  • A procedure is required for A and B to obtain their shared key
  • For n parties to communicate directly, about n2 keys are needed (serious drawback in practice…)
37
Q

Block Ciphers vs. Stream Ciphers

A

A block cipher is an encryption scheme that breaks up the plaintext message into strings (blocks) of a fixed length l and encrypts one block at a time.

A stream cipher is one where the block-length is 1

38
Q

Caesar Cipher (n=3)

A

If we use the algorithm of simply moving each letter nplaces down the alphabet then the original alphabet we were using, or the plain text becomes a cipher text as follows:

a →d

b→e

c→f

39
Q

Mono-alphabetic substitution ciphers

A

Let K be the set of all permutations on the alphabet A. Define for each K ∈ K an encryption transformation eK on

strings x = x1x2…xn ∈. M as

eK(x) = K(x1)K(x2) · · · K(xn) = c1c2…cn = c

To decrypt c, compute the inverse permutation dK(c) = (eK(x))-1

eK is a mono-alphabetic substitution cipher.

Example: ROT13: shift each letter by 13 places. In Unix: „tr a-zA-Z n-za-mN-ZA-M“

40
Q

Security of such substitution

A

Huge key space: 26 letters = 26! Keys, but:

  • Easily broken by analysing the frequency of letters in texts written in a certain language
  • Tables can be used for pairs of letters, or forbidden pairs…
  • Computers can break such „encryption“ in real time.
41
Q

Improvement: Homophonic Substitutions

A

Idea:

  • Map groups of letters into new groups
  • Expand the alphabet (numbers, special characters)

Important:

  • Try to find a mapping that results in an equal distribution of characters; this reduces the risks of attacks based on a letter frequency analysis

Problem:

  • If an attacker gets access to plain and cipher text of one message: Game Over….
  • N.B.: The plain text is in many cases partly known
42
Q

Vigenère-Cyphers

A
43
Q
  • Attacking Vigenère
A

If the length of the key is known, split text accordingly; then:

  • Each block uses a Caesar Cipher.

Example: length = 4

  • take 1., 5., 9., etc. character and attack with a letter frequency analysis
  • Continue with 2., 6., 10., ..

If the length is unknown: try to guess it and attack it as above

  • Computers were built for stupid tasks like this…
44
Q

One-time pad

A
45
Q

Transposition Ciphers

A
  • Transposition does not change the letters itself, but their position in a text
  • Example: Write text in groups of 5 letters, and read it in columns
46
Q

Composite Ciphers

A

Ciphers based on just substitutions or transpositions are in general not secure

  •  Ciphers need to be combined.

But:

  •  Two substitutions are actually only another substitution,
  •  Two transpositions are actually only one transposition,

A substitution followed by a transposition makes a new and (presumably) more secure cipher.

  •  Difficult to do by hand → invention of cipher machines
47
Q

Properties of the Enigma

A

A letter never maps to itself

Encryption and decryption works with identical settings

2x1020 different keys

Code books were used to transport the keys:

  •  A distinct setting of rotors for each day to encrypt a message („session“) key
  •  Individual message keys were used to encrypt transmissions
  • The Enigma was believed to be very secure
  • this was in fact true, compared to the state of the art in encryption at that time
  • However, the scheme was broken…
47
Q

Properties of the Enigma

A

A letter never maps to itself

Encryption and decryption works with identical settings

2x1020 different keys

Code books were used to transport the keys:

  •  A distinct setting of rotors for each day to encrypt a message („session“) key
  •  Individual message keys were used to encrypt transmissions
  • The Enigma was believed to be very secure
  • this was in fact true, compared to the state of the art in encryption at that time
  • However, the scheme was broken…
48
Q

Weaknesses of the Enigma scheme

A
  •  The machine (or parts of it) became accessible to the adversary
  •  Certain specifics of the ciphering scheme

plus:

  •  The adversary spend enormous effort on breaking the scheme (Bletchley Park, Polish Scientists)
  •  Lots of cipher text was available

Plaintext Attack : If a certain word of the plain text is known, one can determine the positions in the cipher text, where this word possibly appears.

49
Q

Block ciphers & stream ciphers

A

Block ciphers: encrypt sequences of “long” data blocks without changing the key

  • security relies on design of encryption function
  • typical block length: 64 bits, 128 bits

Stream ciphers: encrypt sequences of “short” data blocks under a changing key stream

  • security relies on design of key stream generator
  • encryption can be quite simple, often XOR
  • typical block length: 1 bit, 1 byte, 8-bit word
  • *-> Example: WEP encryption in IEEE802.11b**
50
Q

WLAN Security Threat Model

A
  • *Four main threats:**
  • *1. Intruder (user authentication)**

2. Evesdropping

3. Man in the middle attack (fake AP)

4. Back door (rogue AP)

51
Q

Wired Equivalence Privacy

A

Shared key between

  • Stations.
  • An Access Point.

Extended Service Set

  • All Access Points will have same shared key.

No key management

  • Shared key entered manually into

Stations

Access points

Key management nightmare in large wireless LANs

52
Q

Properties of Vernam Ciphers

A

The WEP encryption algorithm RC4 is a Vernam Cipher:

53
Q

Block cipher modes

A

Block ciphers modes offer different security and error propagation characteristics

Electronic code book (ECB): blocks are encrypted independently under the same key

Cipher block chaining (CBC): cipher block Ci depends on the previous block Ci-1

Output feedback (OFB): block cipher used as a key stream generator

Cipher feedback (CFB): block cipher used as a data dependent key stream generator

53
Q

Block cipher modes

A

Block ciphers modes offer different security and error propagation characteristics

Electronic code book (ECB): blocks are encrypted independently under the same key

Cipher block chaining (CBC): cipher block Ci depends on the previous block Ci-1

Output feedback (OFB): block cipher used as a key stream generator

Cipher feedback (CFB): block cipher used as a data dependent key stream generator

54
Q

ECB vs. CBC

A
55
Q

CBC

A
56
Q

Advantages and Limitations of CBC

A
57
Q

OFB

A
58
Q

OFB Advantages and Limitations

A
59
Q

CTR (Counter)

A
60
Q

CTR: Advantages and Limitations

A
61
Q

Product Ciphers

A

A product cipher or composite cipher is built from simple operations offering complementary protection.

Example: a substitution-permutation network

  • “S-Boxes” confuse input bits.
  • “P-Boxes” diffuse bits across S-box inputs
62
Q

Properties Prdouct Ciphers

A

Important Properties :

  • Completeness (dependence): Each output bit depends on every input bits.
  • Avalanche effect: flipping one input bit changes approx. half the output bits.
63
Q

DES

A
64
Q

3DES/2, 2DES and 3DES/3

A

56 Bit DES is vulnerable to brute force attacks

We can use multiple DES

  • Take** *X keys and apply DES y times: 2DES/2, 3DES/2, 3DES/3
  • *We can effectively extend the length of encryption keys using existing**

DES

  • Using two keys to extend the key length to 112 bits, making DES much more secure against brute-force attacks

Notes on 2DES/2:

  • 2DES/2 uses just as many keys as 3DES/2, extending the key length to 112
  • However, 2DES/2 is vulnerable to the meet-in-the-middle attack
65
Q

2DES

A
66
Q

3DES/2

A
67
Q

Feistel Cipher

A
68
Q

AES

A
69
Q

AES 2

A
70
Q

Random Numbers

A

Cryptography uses random numbers for:

    • Generating symmetric keys
  • initailizing values
  • nounces

BUT: Deterministic machines can never produce true statistically random numbers

70
Q

Random Numbers

A

Cryptography uses random numbers for:

    • Generating symmetric keys
  • initailizing values
  • nounces

BUT: Deterministic machines can never produce true statistically random numbers

71
Q

Natural sources for random generators

A

Thermal Nouse, e,g, agitation of electrons inside an electrical conductor

radioactive decay

cosmic radiation

72
Q

PRNGS

A

Pure random numbers often too hard to get

  • numbers that are unpredictable and cannot be reproduces are acceptable
  • a PRNG is deterministic algorithm which given a truly random binary sequence of length k, outputs a binary sequence of length k, outputs a binary seq. of length I >> k, which appears to be random.

Polynomial time statistical tests:

  • no Pat can distinguish an output seq. of the PRNG and a truly random seq.

Next-bit test:

  • there is no polynomial time algorithm which on input of the first/bits of an output seq. s , ca predict the I+1 st bit of s with a prob. greater than 0.5
73
Q

CSPRNGs

A

Cryptographically secure PRNGs (CSPRNGs)

  • A CSPRNG is a PRNG which passes the next bit test under hypothesis such as intractability of factoring integers.

Security of many systems critically depends on the quality of a PRNG/CSPRNG

74
Q

RND Sources in Computers

A
  • Mouse movement (coordinates)
  • Combination of: Process id, clock ticks since boot, username, time, internal system counters, page fault counts, etc.
  • Bits from (compressed) sound card input

Algorithmic Schemes (linear congruential Generators)

Xn+1 = (a . xn+c) mod m

problem if alg. is known and the seed can be guessed, then the seq. can be reproduces

  • seed must be kept secret and must be long enough to defeat brute force attacks
75
Q

Linear Congruential Generators

A

Xn+1 = (a . xn+c) mod m

x0=0 a=1=c m = 20

  • if m is prime then carefully chosen values of a can be good enough
  • x0 should be sufficiently large and random
  • algorithm should be restarted once in a while
76
Q

Blum Blum Shub

A

xn+1= (xn)2 mod m

where m=p*q is the product of two large primes p and q

plus:

  • a few more req
  • a mapping of the output

it can be shown that this is a csprng by relating the prediction of values to integer factorization

77
Q

Other methods for RGN

A
  • use of ciphers as DES to produce random numbers from seeds: a good cipher produces an output independent of the input
  • ciphers in off ort car-mode based on an initial seed
78
Q

cryptographic keys

A

Most cryptographic algorithms take a key as one of their inputs

Kerckhoffs’ principle: do not rely on the secrecy of cryptographic algorithms; only the keys have to be kept secret

State of the art: standardized algorithms that have been examined quite intensively and are often the strongest part in a security architecture

Good key management practices are required to reap the benefits of strong cryptography

79
Q

Problem with sending secret key in symmetric key encryption

A
  • we can send the keys on a different communications channel, e.g. by courier
  • We can also shift the problem in time and exchange keys at a more convenient moment
  • We can combine both methods and meet in person to exchange keys for future use
80
Q

Key exchange without secrets

A

ISE (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions