  We propose measuring the arrival time difference of Fast Radio Bursts (FRBs)
along two adjacent sightlines as a new probe to dark matter substructures on
scales down to $\sim 1\,$AU. We discuss two observational scenarios in which it
may be possible to place interesting constraints on such models through
monitoring repeating FRB sources: 1) By sending radio receivers to space to
form a baseline of tens of AU or more and measuring the temporal variation of
the arrival time difference between receivers. 2) By measuring the temporal
variation of the arrival time difference between two lensed images of one
strongly lensed repeater. In both scenarios, obtaining interesting constraints
requires correlating the voltage time series to measure the radio-signal
arrival time to sub-nanosecond precision. We find that two radio dishes
separated by $20\,$AU may be sensitive to the enhancement of small-scale
structures at $\sim 10^{-8}M_\odot$ masses in the QCD axion dark matter
scenario or from an early epoch of matter-domination with a reheating
temperature up to 60 MeV. Other dark matter models such as those composed of
$\sim 10^{-13}M_{\odot}$ primordial black holes produced during inflation would
also be probed by this method. We further show that a strong lensing situation
of multiple images provides an equivalent $\sim 2000\,$AU baseline, which can
be much more sensitive but with the uncertainty that intervening ISM
decoherence may degrade the timing precision and that spatial variation in the
FRB emission spot may result in confounding signals. We show that the lensing
magnifications of Type Ia supernovea constrain a similar quantity to such FRB
timing, with present limits being equivalent to ruling out the same parameter
space that would be probed by a $0.14~$AU baseline.
