>Their attack uses binary search to recover the private RSA key after 1023 client logins
I know this is from the initial paper but it is great to see practical examples of algorithms taught in college/uni.
I always had trouble understanding why we are learning such hard topics to find the number 5 in a sorted list of 10 numbers.
To keep things on topic.
>The patches that MEGA developed to mitigate the original key recovery attack are
effective against our improved attack as well, so updated clients are not vulnerable to the
techniques presented in this work. However, our optimized cryptanalysis underscores the
ongoing risk to unpatched clients
Great to hear that their patches fix the root of the problem but this paper has now significantly reduced the complexity of carrying out the attack.
Binary trees and by extension search show up throughout my career - turning problems into a logarithmic search of the solution space and dynamic programming are like the two most practical data structure and algorithms I’ve been exposed to for truly truly solving hard problems.
The OP proudly showed off a custom B-Tree implementation for a problem where a sorted array and binary search would be far simpler and much faster in practice.
Applying even a smidge more CS knowledge could have resulted in using Netwon's Iteration as the lookup, which is the almost perfectly optimal solution: just one random I/O to do a lookup even with a cold cache!
>I always had trouble understanding why we are learning such hard topics to find the number 5 in a sorted list of 10 numbers.
It is left up to the learner to realize that the list of 10 numbers can be either the left side or right side of a higher node, showing that any binary search of 10 numbers works on 20 numbers and hence on any size sorted-list. Then, it becomes clear why the average search space decrease from N to log n.
Many people find binary search to be a valuable algorithm to use in practice.
Why so much complexity when all Mega has to do to recover the private key is to capture it using JavaScript ? (they can target specific files or users without getting caught)
Readit News
I know this is from the initial paper but it is great to see practical examples of algorithms taught in college/uni.
I always had trouble understanding why we are learning such hard topics to find the number 5 in a sorted list of 10 numbers.
To keep things on topic.
>The patches that MEGA developed to mitigate the original key recovery attack are effective against our improved attack as well, so updated clients are not vulnerable to the techniques presented in this work. However, our optimized cryptanalysis underscores the ongoing risk to unpatched clients
Great to hear that their patches fix the root of the problem but this paper has now significantly reduced the complexity of carrying out the attack.
The OP proudly showed off a custom B-Tree implementation for a problem where a sorted array and binary search would be far simpler and much faster in practice.
Applying even a smidge more CS knowledge could have resulted in using Netwon's Iteration as the lookup, which is the almost perfectly optimal solution: just one random I/O to do a lookup even with a cold cache!
It is left up to the learner to realize that the list of 10 numbers can be either the left side or right side of a higher node, showing that any binary search of 10 numbers works on 20 numbers and hence on any size sorted-list. Then, it becomes clear why the average search space decrease from N to log n.
Many people find binary search to be a valuable algorithm to use in practice.
Probably.
https://xkcd.com/538/