TIL: Colliding Secure Hashes, FIFO and LRU Cache, GPS

Feb 17, 2025

Colliding Secure Hashes

It’s interesting to see Pollard’s Rho Algorithm can be used in finding collision. Intuitively, this works because: the hash we try to break is a secure hash -> so it behaves like a PRF -> by the birthday paradox, we can find collisions in the same amount of time as naive birthday bruteforce algorithm.

Figure showing four random walks (trails) converging to a collision point, illustrating parallelized Pollard's rho collision search, with distinguished points marked as open circles

The Parallel Pollard’s Rho method explores the time-space tradeoff (controlled by the distinguisher function) + parallelization. For a nn-bit hash and a distinguisher function enforcing the first kk-bit of the hash to be 0, a quick math gives us the following:

  • Space Complexity: O(2(n−k)2)O(2^{\frac{(n-k)}{2}}).
  • Time Complexity: O(2k∗2n−k2)O(2^k * 2^{\frac{n-k}{2}}).
  • As expected, the product of them is O(2n)O(2^n).

FIFO can be Better than LRU

Wonderfully simple ideas and very intuitive!

Diagram of a logically ordered cache queue showing insertion, eager and lazy promotion, passive and quick demotion, and removal of entries *Cache Abstraction*

Lazy Promotion

  • Their assumptions about popularity decay are basically in line with what I’ve encountered in real life.
  • Notably, this strategy also applies to the traditional LRU (simply replace eager promotion with lazy promotion). But, in such case, simply using FIFO is a much wiser choice.

Quick Demotion

  • Q: How to balance the size of the probationary FIFO queue? (parameter selection)
  • Q: Can we get more benefit by adding hierarchy (many FIFO queues with different sizes) to QD? What’s the tradeoff here?

GPS

An extremely well crafted articles discussing details about GPS. I particularly enjoy its visualizations a lot.

The authors cover a lot topics including

  • Trilateration on 2D plane
  • Time of Flight and Synchronization
  • Keplerian Elements
  • Inaccuracies
    • Time
    • Signal Propagation
  • Signal Processing and Coding

A few wonderful illustrations

(x−x1)2+(y−y1)2+(z−z1)2=v×(t1−b)(x−x2)2+(y−y2)2+(z−z2)2=v×(t2−b)(x−x3)2+(y−y3)2+(z−z3)2=v×(t3−b)(x−x4)2+(y−y4)2+(z−z4)2=v×(t4−b)\begin{aligned} \sqrt{(x - \textcolor{red}{x_1})^2 + (y - \textcolor{red}{y_1})^2 + (z - \textcolor{red}{z_1})^2} &= v \times (\textcolor{red}{t_1} - b) \\ \sqrt{(x - \textcolor{green}{x_2})^2 + (y - \textcolor{green}{y_2})^2 + (z - \textcolor{green}{z_2})^2} &= v \times (\textcolor{green}{t_2} - b) \\ \sqrt{(x - \textcolor{blue}{x_3})^2 + (y - \textcolor{blue}{y_3})^2 + (z - \textcolor{blue}{z_3})^2} &= v \times (\textcolor{blue}{t_3} - b) \\ \sqrt{(x - \textcolor{olive}{x_4})^2 + (y - \textcolor{olive}{y_4})^2 + (z - \textcolor{olive}{z_4})^2} &= v \times (\textcolor{olive}{t_4} - b)\end{aligned}

With this set of equations, we can solve for the x, y, and z coordinates of our position. But remember the complications: 1) how do we represent the coordinates of the satellites, 2) how do we calculate time of flight for satellite signal, 3) how can we successfully decode the signal, etc. {: .caption }

Illustration of Earth with satellites positioned along the equatorial plane, showing that signals from these satellites cannot distinguish between a point and its mirror image across the equator *If all GPS satellites are geostationary, we cannot differentiate the north and south atmosphere.* Diagram of multiple satellite orbital planes around Earth, with a heat-map overlay showing the number of visible satellites, ranging from 6 to 16, at each point on the globe *The number of visible satellites from every point on Earth, with density.* Step-by-step diagram of GPS signal decoding: the carrier-removed signal, a code replica, their product, the summed areas, and the difference of summed areas used to recover the satellite's source data *This shows how the signal is decoded. Since the code has high auto-correlation and low cross-correlation, we can decode the signal from the correct satellite.*

Final Words

The final words are really touching:

It’s fascinating how much complexity and ingenuity is hidden behind the simple act of observing one’s location in a mapping app on a smartphone. What I find particularly remarkable is how many different technological advancements were needed for GPS to work.

Just the satellites themselves required the development of rockets, mastery of orbital controls, and manufacturing prowess to build devices capable of withstanding the extremes of space.

Precise time tracking was made possible by the invention of an atomic clock, while advancements in radio transmission and clever coding algorithms allowed the very weak signal sent by satellites to be correctly deciphered on Earth by receivers, which were in turn dependent on microchips and the digital revolution.

It’s hard not get inspired by the relentless drive of people who kept pushing science and technology forward. All of their work made GPS an indispensable tool in our everyday life.