# On BDD with Predicate: Breaking the “Lattice Barrier” for the Hidden Number Problem

Nadia and I put our pre-print and our source code online for solving bounded distance decoding when augmented with some predicate $f(\cdot)$ that evaluates to true on the target and false (almost) everywhere else. Here’s the abstract:

Lattice-based algorithms in cryptanalysis often search for a target vector satisfying integer linear constraints as a shortest or closest vector in some lattice. In this work, we observe that these formulations may discard non-linear information from the underlying application that can be used to distinguish the target vector even when it is far from being uniquely close or short.

We formalize lattice problems augmented with a predicate distinguishing a target vector and give algorithms for solving instances of these problems. We apply our techniques to lattice-based approaches for solving the Hidden Number Problem, a popular technique for recovering secret DSA or ECDSA keys in side-channel attacks, and demonstrate that our algorithms succeed in recovering the signing key for instances that were previously believed to be unsolvable using lattice approaches. We carried out extensive experiments using our estimation and solving framework, which we also make available with this work.

# UDP Idle Scanning

We describe a (seemingly) new scanning technique for determining whether a UDP port is open without sending IP packets with the scanner’s IP to the target. It is a (UDP specific) variant of the TCP Idle Scan1 that was uncovered 20 years ago. It proceeds similarly to the TCP RST Ratelimit Scan2, but uses ICMP rate limiting as the side-channel. It only works for UDP protocols where we can solicit a reply.3 For a list of such protocols, see e.g. ZMap’s UDP Probe Module4 or NMap’s payloads5.

## Scan

Consider three machines:

S : Scanner

Z : Zombie, we assume Z is sufficiently close to S to allow burst IP packets to arrive in, well, bursts. We also assume the zombie is running a Linux kernel with version at least v3.18-rc16 and with default options set. In particular, we assume icmp_msgs_burst = 50 (other small values are fine, too) and icmp_ratemask = 0x1818. We will make use of the Destination Unreachable bit being set.7

T : Target, we wish to check if the target is listening on $UDPPORT, speaking a protocol for which we can solicit a reply (e.g DNS, PCAnywhere, NetBios, SIP or anything speaking DTLS, see above). The scan proceeds as follows: 1. S(Z) -> T: 1 UDP packet to $UDPPORT at T, spoofed from Z’s IP address
2. S -> Z: 49 UDP packets to a closed port from 49 different spoofed source IPs (to prevent per host ICMP rate limiting to kick in)
3. T -> Z: If the target port is open then the target will respond to Z. Otherwise an ICMP Destination Unreachable message is sent from the target to the zombie.
4. Z -> T: If a UDP response was generated, the zombie will respond with ICMP Destination Unreachable message to the target. Otherwise, nothing happens.
5. S -> Z: 1 UDP probe to some closed port.
6. Z -> S: If the zombie has exhausted its budget of 50 burst messages by responding to the target, the scanner will not receive a response. Otherwise, it will.

Note: A variant of this scan is to target icmp_msgs_per_sec which is 1000 by default.