Algorithms

Question 1

DoS via Algorithmic Complexity Attacks

Answer 1

• key idea: attacker crafts input to elicit worst case behavior from the target
• examples: Quicksort worst case O(n^2), weak hash table algo attacks

Question 2

Space complexity attacks

Answer 2

• example: Zip bombs (recursive zip files that fill your computers hardrive, render it unusable)
• key idea: fill all memory space to make running all processes impossible or very slow

Question 3

Defense against algorithmic complexity attacks

Answer 3

• understand algos and data structures, create programs with safe ones
• limit user input by: limiting volume & influence (input validation!)
• limit and monitor resource use

Question 4

Side-Channel Attacks

Answer 4

• instead of attacking the target directly, measure or exploit info leaked through indirect effects and low-level implementation details
• ex: string comparison for secrets vulnerable if program exists when first comparison is false