Parity checking:
- A way of error detection
- Detect any single error, but won’t detect two error
- It doesn’t tell you where the error is, can’t correct it
- e.g. 11100011001 – parity is odd/ even, depending on the number’s of 1s
- 6 1s – even parity
- Or by adding the digits modded by 2 – get 0 (even parity)
- So all messages have even parity
- e.g. Alice want to send the message 1101 – odd parity
- She need to add a parity bit at the end – 11011 → even parity
- Bob check to see parity is even, throw away the parity bit and has the message
1101
- e.g. Alice want to send 1001 – even parity
- She put 0 at the end as parity bit
- Send 10010
- Bob has even parity, throw away the parity bit
Practice Assignment: Parity checking
, Hash function:
- H is a function has fixed sized output, H can take in any strings – always returns the
same length output
- H is effectively computable: input could be large/ small but important cases is where the
input is large
- Output of hash function – hash value
- e.g. parity
- H(X) = (sum of bits of X) mod 2
- 1 bit hash function
- Can use a hash function to detect any number of errors
- Collision free: would work perfectly of we never had two inputs mapped to the same
output
- 1-1 / injective function to detect any error → too strong to be feasible
- Birthday method for breaking a hash function:
- H(person) = birthday
- H(henry) = 0105
- Likely two people to have the same hash value
- Fraud technique:
- Change the file so it says what you want
- It will almost certainly not have the same hash value
- Start changing it in inconsequential ways (different punctuation, more spaces…)
and keep checking the hash value
- How is the "birthday problem" used to create a hash collision for a fraudulent purpose?
- Different plain text results in the same hash value.
- Make hash value identical, by making huge number of small changes
- The key is that a digital signature is often applied to the hash value of a
document, not the document itself. So, if the attacker can get you to sign the
legitimate document, they can then replace it with the fraudulent one. Because
both documents produce the same hash, the digital signature will still be valid,
and the fraud is complete
Practice Assignment: Hash functions
- A way of error detection
- Detect any single error, but won’t detect two error
- It doesn’t tell you where the error is, can’t correct it
- e.g. 11100011001 – parity is odd/ even, depending on the number’s of 1s
- 6 1s – even parity
- Or by adding the digits modded by 2 – get 0 (even parity)
- So all messages have even parity
- e.g. Alice want to send the message 1101 – odd parity
- She need to add a parity bit at the end – 11011 → even parity
- Bob check to see parity is even, throw away the parity bit and has the message
1101
- e.g. Alice want to send 1001 – even parity
- She put 0 at the end as parity bit
- Send 10010
- Bob has even parity, throw away the parity bit
Practice Assignment: Parity checking
, Hash function:
- H is a function has fixed sized output, H can take in any strings – always returns the
same length output
- H is effectively computable: input could be large/ small but important cases is where the
input is large
- Output of hash function – hash value
- e.g. parity
- H(X) = (sum of bits of X) mod 2
- 1 bit hash function
- Can use a hash function to detect any number of errors
- Collision free: would work perfectly of we never had two inputs mapped to the same
output
- 1-1 / injective function to detect any error → too strong to be feasible
- Birthday method for breaking a hash function:
- H(person) = birthday
- H(henry) = 0105
- Likely two people to have the same hash value
- Fraud technique:
- Change the file so it says what you want
- It will almost certainly not have the same hash value
- Start changing it in inconsequential ways (different punctuation, more spaces…)
and keep checking the hash value
- How is the "birthday problem" used to create a hash collision for a fraudulent purpose?
- Different plain text results in the same hash value.
- Make hash value identical, by making huge number of small changes
- The key is that a digital signature is often applied to the hash value of a
document, not the document itself. So, if the attacker can get you to sign the
legitimate document, they can then replace it with the fraudulent one. Because
both documents produce the same hash, the digital signature will still be valid,
and the fraud is complete
Practice Assignment: Hash functions
