Authenticating Internet Routing
Using Zero-Knowledge Proofs
Jacob D. White
A-4: Advanced Research in Cyber Systems
Email: jdwhite@[Link]
Mentor: Michael Dixon
Co-Mentor: Boris Gelfand
Collaborator: Zachary DeStefano
August 9th, 2023
Managed by Triad National Security, LLC., for the U.S. Department of Energy’s NNSA. LA-UR-23-29806 1
Internet Routing: The Sky-High View
The Internet is a complex “network of networks”, allowing computers to
route messages to each other across the globe.
Figure: US high-speed fiber optic connections (Lumen 2023)
2
Internet Routing: The Sky-High View
■ Computers send data Internet Infrastructure
across routers Registries &
Trust Anchors
■ Organizations form a
network of routers
■ Routers use policies Organization
or ISP
and protocols to find
and communicate
with each other on the
Internet Global
Internet
3
Internet Routing for ISPs and Organizations
An organization manages an Autonomous System (AS) or domain of
routers. Routing policies are defined internal or external to the domain.
Autonomous Internal (e.g. OSPF) Autonomous
System (AS) System (AS)
4
Internet Routing for ISPs and Organizations
An organization
Problem:manages
RoutersanwhoAutonomous
lie about how System (AS)network
they route or domain of
routers. data
Routing
canpolicies are defined
cause serious internaland
disruptions or external to the domain.
privacy issues!
Autonomous Internal (e.g. OSPF) Autonomous
System (AS) System (AS)
Traffic Diversion (Blackholing)
5
Internet Routing for ISPs and Organizations
An organization
Problem:manages
RoutersanwhoAutonomous
lie about how System (AS)network
they route or domain of
routers. data
Routing
canpolicies are defined
cause serious internaland
disruptions or external to the domain.
privacy issues!
Autonomous Internal (e.g. OSPF) Autonomous
System (AS) System (AS)
Traffic Diversion (Blackholing) Interception Attack
6
Internet Routing for ISPs and Organizations
An organization manages an Autonomous System (AS) or domain of
routers. Routing policies are defined internal or external to the domain.
ISP Internet External (BGP) ISP Internet
A A
B B
Routing Routing
Policy Org’s Network Policy
Transit (Customer-Provider) Peers
7
Internet Routing for ISPs and Organizations
An organization
Problem:manages
RoutersanwhoAutonomous System
lie about their routing(AS) or domain
network data of
routers. can
Routing policies
cause seriousare defined internal
disruptions or external
and privacy to the domain.
issues!
ISP Internet External (BGP) ISP Internet
A A
B B
Routing Routing
Policy Org’s Network Policy
Transit (Customer-Provider) Peers
Policy Violation
8
Internet Routing for ISPs and Organizations
An organization
Problem:manages
RoutersanwhoAutonomous System
lie about their routing(AS) or domain
network data of
routers. can
Routing policies
cause seriousare defined internal
disruptions or external
and privacy to the domain.
issues!
ISP Internet External (BGP) ISP Internet
A A
B B
Routing Routing
Policy Org’s Network Policy
Transit (Customer-Provider) Peers
Policy Violation Interception Attack
9
Internet Routing for ISPs and Organizations
Key Questions:
1. How can we authenticate network operations, having routers learn
from the global network, and behave according to policy?
2. How can we avoid leaking private information about organizations’
networks and relationships?
10
(Non-interactive) Zero-knowledge Proofs
Zero-knowledge proofs (ZKPs) allow us to prove that a claim IS true without
revealing WHY it is true, even if the prover is considered untrusted and malicious.
Proof
Computation,
Schematics,
& Information
Convert
ZKP
Retain &
Example Claim.
Claim Claim
Claim “The packet can reach
Router Y from X, even if
Router Z goes offline”
11
Features of (Non-interactive) Zero-knowledge Proofs
Zero-knowledge proofs (ZKPs) allow us to prove that a claim IS true without
revealing WHY it is true, even if the prover is considered untrusted and malicious.
Miniscule Footprint Fine-grained Control Composable Expanded Trust
OLD
NEW
~3k Bits
Some ZKP variants are ZKPs give fine-grained ZKPs can be collected Portable proofs
tiny, often only slightly control over secret and combined into new extend our trusted
larger than a regular information, yet allows ZKPs without growing view beyond that of
QR code trustless verification in size our own system
12
ZKPNet: An Overview
Developed a prototype Rust library which provides useful gadgets for
authenticating network routing attestations using ZKPs
Network Applications
ZKP Protocol
ZKPNet Routing
library ZKPNet Protocol API
Gadget API
Network routing /
ZKP Circuit Network API system backend
API
(e.g. FRRouting)
ZKP backend Arithmetic OS
(e.g. Arkworks) constraints
Rust Link Layer
13
Demo: Proving Route Reachability
Group A wants to send important data to Group C, but will need to go
through Group B first. A and C first want to verify that B can deliver the
data, but Group B is unwilling to reveal details about the network for
security reasons. How does Bob prove this?
Group B
Group A Group C
ZKP
14
Results: ZKPNet Demo Benchmarks
Using realistic OSPF entries for internal routing, we have constructed
zero-knowledge proof for route reachability for a single hop. Benchmarks
were performed on a Apple M1 Max CPU with 32 GB of memory.
Proving Time Verification
ZKP # of Proof Size
(Latency / Time
Technique constraints (Bandwidth)
Delay) (Latency)
Single Proof 104 224 B* 468.03 ms 2.7165 ms
Depth-2
Recursion on 13976 299 B* TBD TBD
Proof
*Estimated from Groth16 proof sizes with MNT4&6 curves
15
Looking Ahead: Feature Support for Routing Auth.
BGPSec (best
(worst auth)
(deployed)
so-BGP
ZKPNet
S-BGP
RPKI
auth)
IRR
Legend
Network Route Integrity Complete
Partial
Comm/Bandwidth Efficiency
Missing/Bad
Dynamic/Adaptive Recovery
Varies
Trustless Authentication
Privacy Preservation
16
Future Work: ZKP Compiler for Verifiable Routing
as-num: 64496
import: {
from AS64497 at [Link]
action pref=0;
accept community
Routing
.contains(GRACEFUL-SHUTDOWN);
from AS64497 action pref=10 accept ANY; Policy Spec
(RPSL)
6 7
from AS64496:AS-SECRET # ...
} except {
from AS64497 at [Link] accept RS-BOGONS-V4;
# ...
}
router bgp 64496 # ... ZKP
neighbor [Link] route-map AS64497-in in
neighbor [Link] route-map AS64497-out out
!
route-map AS64497-in permit 10 Routing
Published
set local-preference 0 Config
RPSL Spec
match community graceful-shutdown (Cisco-IOS)
route-map AS64497-in deny 10
match ip address prefix-list bogons-v4
!
# ...
17
Future Work: Using ZKPs to Inform RL-based SDNs
Software Defined Networking
(SDN) routers take a different Environment
approach: adopt Reinforcement (Network)
Learning (RL) techniques to
decide optimal routing policies.
State
SDN requires much more data
(often sensitive!) to inform routers. ZKP
Action
Feedback
Human-on-the-loop approach Agent
gives verifiable ZKP claims, (Router)
allowing RL-based routers to
reason about secret info as well!
18
Conclusion
■ ZKPs can provide both privacy and Internet Infrastructure
authenticated routing guarantees,
ensuring conformance to both protocol
and policy specifications.
■ Since ZKPs do NOT rely on key
infrastructure, they are a promising ZKP
tool for authenticating routing in a ZKP
distributed environment. Auth
■ ZKPs will likely increase proving and
verification times, with many
overhead and maintenance
challenges to consider before
z
widespread adoption. ZKP
19
Backup
20
Integrating ZKP Information
into RL-based SDNs
(Backup)
23
Software-Defined Networking (SDN) Overview
Hardware routing not very complex – “on-chip” accelerators to perform
specialized routing tasks very quickly
… also not very flexible
SDNs allow software itself to decide how to best route incoming
packets / react to changing scenarios
UNCLASSIFIED 24
Reinforcement Learning (RL) Overview
Agent (here, router) performs action given current state, environment
(here, ML model/network sim) impacted, new state produced with
reward/punishment for said action, back to agent.
Environment
State
Action
Feedback
Agent
(Router)
UNCLASSIFIED 25
Background: Resilient and Secure Cyber Networks
Traditional routers use heuristic networking
protocols, such as BGP, to route and
deliver messages between clients.
Traditional protocols are not resilient to
drastic changes injected by adversaries.
Recent research has focused on
learning-based software defined
networking (SDN) routers that use
reinforcement learning to ingest network
state data and optimally route.
26
Challenge: Input Validation for Learning-based Routers
SDN (e.g. AI-based) routers require extra
information about the network from other hosts to
quickly adapt to new changes.
Problem I: Some hosts, including neighbors,
may be malicious.
Problem II: Network details and/or messages
may contain sensitive or proprietary information.
27
Challenge: Input Validation for Learning-based Routers
SDN (e.g. AI-based) routers require extra
information about the network from other hosts to
quickly adapt to new changes.
Problem I: Some hosts, including neighbors,
may be malicious.
Problem II: Network details and/or messages
may contain sensitive or proprietary information.
28
Solution: ZKPs for Network Security Properties
We can authenticate relevant peer-provided
information used by smart routers using
zero-knowledge proofs.
Properties that are true on one end of the
network can be communicated to the other side ZKP
with little-to-no trust.
We will use succinct ZKPs, so they will be small
enough to add minimal overhead to the
network.
29
Single-Prover ZKPs
(Backup)
32
Zero-Knowledge Proof for Where’s Waldo?
Example. Proving that you know the solution to Where’s Waldo?
33
Zero-Knowledge Proof for Where’s Waldo?
Example. Proving that you know the solution to Where’s Waldo?
Traditional Proof: Circle Waldo’s location
34
Zero-Knowledge Proof for Where’s Waldo?
Example. Proving that you know the solution to Where’s Waldo?
Traditional Proof: Circle Waldo’s location
Problem
This kind of proof leaks all information about Waldo’s location, much more than
simply that you have knowledge of the location (not zero-knowledge)!
35
Zero-Knowledge Proof for Where’s Waldo?
Zero-knowledge Protocol
1. Cut out a Waldo shaped hole in a much larger piece of paper
2. Position the hole over Waldo’s location
Slide under paper
The sheet acts as an
obfuscating mask for
Waldo’s location To verifiers, the book underneath could
hypothetically be in any random orientation
36
Zero-knowledge Proofs: High Level View
Proof
Computation,
Schematics,
& Information
Convert
ZKP
&
Retain Example Claim.
Claim Claim “The packet can reach
Claim Router Y from X, even
if Router Z is offline”
37
Zero-knowledge Proofs: High Level View
Proof
The Zero Knowledge Proof
Convert replaces the need for
sensitive proof information
(effectively completely redacting
ZKP the original proof)
&
Retain
Claim Claim
Claim The Claim can be quickly verified
without any knowledge of the
original proof.
38
Zero-Knowledge Proofs and Network Authentication
Zero-knowledge proofs (ZKPs) allow us to prove that a claim IS true without
revealing WHY it is true, even if the prover is considered untrusted and malicious.
zkSNARKs are special ZKPs that are tiny and non-interactive
Inputs:
Audit Logs Outputs:
Schematics Results
Policies &
Signal Analysis ZK Proof of
Encryption Keys O(1) Network
Attestations size Integrity
etc. O(n) O(n*log(n)^k)
size size
*with tweaks
Homomorphically Encrypted *
39
Features of (Non-interactive) Zero-knowledge Proofs
Zero-knowledge proofs (ZKPs) allow us to prove that a claim IS true without
revealing WHY it is true, even if the prover is considered untrusted and malicious.
Ideal Secrecy Miniscule Footprint Fine-grained Control Composable
~3k Bits
Secrets are NOT Proofs are tiny, often Exacting control over ZKPs can be collected
revealed even if the only slightly larger than need-to-know while and combined into new
cryptography is a regular QR code enabling trustless ZKPs without growing
completely broken verification in size
40
Cryptographic Proof Systems
Cryptographic proof systems have variable completeness and
soundness. For non-interactive zero-knowledge proofs we care about:
(Completeness) ℙ[true statement AND verifier accepts] = 1
“Everything true is provable”
(Soundness) ℙ[false statement AND verifier rejects] = 1 - ε
“Low chance that a proof of a false statement is
encountered”
We sacrifice minimal amount of soundness (have to break crypto to
produce counter-example) in order to get valuable proof properties
41
zkSNARK Construction for Verified Computation [BCGTV13]
int myFunction(int a) { Arkworks
int b=a*a-4;
return 3*b+a; Computation
}
Rank-1 Constraint System (R1CS): Arithmetic Proof Representation
Circuit Of Network Robustness
S•A * S•B = S•C
R1CS
1 0 1 0 1 0
a 1 a 1 QAP Zero Knowledge Added
a 1
t0 0 t0 0 t0 0 LPCP Succinctness Added Arkworks
LIP backend
b 0 b 0 b 0
Interactivity Removed
t1 0 t1 0 t1 0 zkSNARK
Verifier
Net View
Prover
View
π zkSNARK for
Network Integrity
42
Spare (Ignored/Skipped)
47
Alert: RPKI is Vulnerable and Risky!
Internet Infrastructure Weaknesses:
Registries &
Trust Anchors
● Centralized trust is a
point of failure
Too Much
Blind Trust! Spoofable! ● Can’t certify entire
Internet route / network
Service
Provider (ISP) ● Keys are a target
and hard to manage
Global
Internet
UNCLASSIFIED 50
Secure and Robust ISP Network Routing
Existing: RPKI Internet Infrastructure
● Trust sources are
points of failure
● Only certifies info of
route’s origin ZKP
ZKP
● Authentication needs
centralized keys
● Can only decide route on
public (often local) info ZKP
UNCLASSIFIED 51
Secure and Robust ISP Network Routing
Existing: RPKI Internet Infrastructure Our Solution: ZKPNet
● Trust sources are ● Trust sources are
points of failure distributed
● Only certifies info of ● Correctly verifies
route’s origin ZKP
arbitrary info
ZKP
● Authentication needs ● No auth keys, only
centralized keys trusted setup
● Can only decide route on ● Also decides with
public (often local) info ZKP
secret global info
52