Case Study
Distributed Meet-in-the-Middle Attack
Implemented a hybrid distributed system to solve exponentially-scaling meet-in-the-middle collision search, with measured scaling on an HPC cluster.
At a Glance
Key Metrics
Scale
512 MPI ranks
Grid'5000 (16 nodes)
Max size
n = 40
9 passes to fit RAM
Speedup
171.6x
n=36 (est.)
Efficiency
33.5%
512 ranks (n=36)
Summary
TL;DR
One-liner
Built a hybrid MPI (sharded distributed dictionary) + OpenMP + AVX2 SIMD implementation on Grid'5000 (16 nodes, 36 cores/node, 192GB RAM/node) scaling to 512 MPI ranks. Solved problem sizes up to n=40 using a 9-pass time-memory tradeoff. Estimated speedup: 171.6x (n=36, 33.5% efficiency) and 120.2x (n=40, 23.5% efficiency).
Background
Context / Problem
Meet-in-the-middle collision search becomes exponentially harder as n increases, quickly exceeding single-node time and memory limits. The goal was to scale to an HPC cluster by solving: distributed memory for the dictionary and high-throughput cryptographic kernels.
Visualization
512 MPI Ranks in Action
Each square below represents one MPI rank across the 16-node Grid'5000 cluster. Toggle between phases to see the difference in communication patterns.
Constraints
Evaluation Plan
Memory-bound
Communication-heavy
Performance verification
Stability at scale
Methodology
Process
Designed the system in phases (fill → probe → verify), then iterated on: dictionary sharding, communication chunking to avoid oversized buffers, OpenMP scheduling for uneven probe workloads, and AVX2 vectorization to accelerate the cryptographic kernels. Implemented a low-overhead sampling strategy (power-of-two stride) and emitted a metrics.csv per run for timing counters and resource usage.
Implementation
Solution
- MPI sharded dictionary (owner-by-hash via murmur64 + modulo) with chunked MPI_Alltoallv for both fill redistribution and batched probe queries.
- OpenMP parallelism within each rank: static scheduling for fill, dynamic scheduling for probe, and OpenMP tasks for asynchronous candidate verification.
- AVX2 SIMD: 8-way Speck64/128 key schedule + encryption/decryption wrappers integrated into fill/probe/verify.
- Memory safety: auto-detect RAM and cap dictionary to 60% with a 40% margin for MPI/OS; time-memory tradeoff via multi-pass execution.
Architecture Diagram
Timing Analysis
Phase Timing Breakdown
At n=40, the probe phase dominates total runtime. The fill phase completes relatively quickly, while probe requires orders of magnitude more time due to dictionary lookups and network round-trips.
n=40 single pass -- probe dominates total runtime by 15:1
Performance
Speedup Comparison
Estimated speedup vs. sequential baseline at different problem sizes. Sequential evaluation becomes infeasible beyond n=29, so larger-n speedups are estimated assuming doubling time per increment in n.
n=40 speedup lower due to 9-pass time-memory tradeoff overhead
Outcomes
Results
Validated end-to-end collision finding at large problem sizes on Grid'5000, including a 9-pass configuration to fit RAM constraints at n=40.
| Metric | Result |
|---|---|
| Max problem size | n=40 (9 passes) |
| Scale | 512 MPI ranks on Grid'5000 (16 nodes; 36 cores/node; 192GB RAM/node) |
| Speedup (n=36) | 171.6x with 33.5% efficiency (512 ranks) |
| Speedup (n=40) | 120.2x with 23.5% efficiency (sum of 9 passes) |
| Phase timing (n=40) | Fill ~ 97-99s; Probe ~ 1453-1454s (probe dominates) |
| Instrumentation | Power-of-two stride sampling + per-run metrics.csv |
Takeaway
Why This Matters
This project is less about cryptography and more about systems engineering at scale: sharded distributed data structures, high-volume all-to-all traffic, CPU kernel optimization (SIMD), and measurement discipline under real cluster constraints.
Systems engineering perspective
Reflection
Learnings
Probe dominates at scale
Dictionary lookup + network communication become the limiting factors as n grows. The probe phase consumed 93.7% of total runtime at n=40.
Instrumentation must be cheap
Sampling-based timing (power-of-two stride) was necessary to avoid perturbing the very performance being measured.
Memory constraints shape algorithms
The 9-pass design enabled n=40 under strict RAM budgeting. Without the time-memory tradeoff, the problem would have been limited to n=36.
Contribution
Role / Authorship
Co-authored the project. Implemented the distributed sharded dictionary, MPI communication patterns (chunked Alltoallv and probe query/response), OpenMP parallel probe + async verification, and the benchmarking instrumentation pipeline.
Future Work
What I'd Do Next
- Reduce dict_probe latency via alternative dictionary layout / hashing and tighter memory locality.
- Explore communication reductions (sharding strategies to reduce remote probes; fewer global collectives).
- Add automated regression benchmarks to catch performance drift across cluster configurations.