Secure Keyed Hashing on Programmable Switches
SipID: (Half)SipHash In the Data Plane
Secure Keyed Hashing on Programmable Switches
S
o
p
h
i
a
Y
o
o
&
X
i
a
o
q
i
C
h
e
n
1
Today’s Data Plane Applications
-
Opportunity for improved
-
Security
-
Privacy
-
Performance
-
Reliability
Implementation
Challenges
Sophisticated
Applications
-
Hardware Implementation Challenges
-
Limited Arithmetic Operations
-
Limited Pipeline Stages
2
Network Applications use Hashing Extensively
I
n
d
e
x
i
n
g
Hash of header fields
used as array index
for hash tables (e.g.,
Jaqen, NetCache)
F
i
n
g
e
r
p
r
i
n
t
i
n
g
Hash stored in
register array as
fingerprint of longer
flow IDs (e.g.,
SilkRoad, P4RTT)
S
a
m
p
l
i
n
g
Pseudo-random hash
compared with
thresholds to sample a
subset of traffic (e.g.,
AROMA, BeauCoup)
3
-
Not a cryptographic function
Significant limitations
-
Insecure as a hash
-
Fast
-
Computationally inexpensive
CRC: Designed to catch
accidental
bit flips, not
intentional
changes
CRC32 is widely used in the data plane
Efficient
Input: 0b11000010
Zero: checksum correct
Checksum: 0b00001111
CRC
Verification
Non-zero: checksum incorrect
4
Vulnerabilities due to CRC32
I
n
d
e
x
i
n
g
F
i
n
g
e
r
p
r
i
n
t
i
n
g
S
a
m
p
l
i
n
g
Collisions that force
table updates and
evictions to go to the
same index
Collisions that
inaccurately group
flow IDs together with
the same fingerprint
Construct hashes that
cause traffic to never
be sampled (bypass
monitoring) or always
sampled (system
overload)
Never sampled!
Always sampled!
5
We need a
secure
hash, do these exist?
-
Yes!
-
E.g., SHA256, Scrypt, Blowfish
-
But, there are some problems…
-
Computationally expensive
-
Complex implementation unfriendly to data plane
-
Inefficient, slow
S
e
c
u
r
i
t
y
S
p
e
e
d
CRC32,
Checksum
SHA256,
Scrypt,
Blowfish
SipID
(HalfSipHash in
the Data Plane)
6
HalfSipHash-
c
-
d
m
1
m
0
Compression Round
Compression Round
m
0
Compression Round
Compression Round
m
1
0xff
Finalization Round
Finalization Round
Finalization Round
Finalization Round
H
a
l
f
S
i
p
H
a
s
h
-
2
-
4
o
n
a
n
8-byte (m=2 words) input
Preprocessing(keys, initial values)
v
0
v
1
v
2
v
3
7
“Compression” Rounds
“Finalization” Rounds
Jean-Philippe Aumasson and Daniel J. Bernstein. 2012. SipHash: A Fast Short-Input PRF.
One Original HalfSipHash Round
n = 5
a = 0b11010010
a <<< 5 =
0b
010
11010
Intermediate Steps:
x
=
a
<
<
5
=
0
b
0
1
0
0
0
0
0
0
y
=
a
>
>
(
8
-
5
)
=
0
b
0
0
0
1
1
0
1
0
b = x OR y = 0b
010
11010
Challenge #1: Limited Arithmetic Operations
-
Circular Bit Shifts
Strawman circular bit shifting
Semantically equivalent slicing
8
Computationally Expensive!
n = 5
a = 0b11010010
a <<< 5 =
0b
010
11010
Intermediate Steps:
x
=
a
<
<
5
=
0
b
0
1
0
0
0
0
0
0
y
=
a
>
>
(
8
-
5
)
=
0
b
0
0
0
1
1
0
1
0
b = x OR y = 0b
010
11010
Challenge #1: Limited Arithmetic Operations
-
Circular Bit Shifts
Strawman circular bit shifting
Semantically equivalent slicing
9
Computationally Expensive!
n = 5
a
<
<
<
5
b[31:0] = a[
26:0
] ++ a[
31:27
]
Challenge #2: Limited Pipeline Stages
Original HalfSipHash Round
10
Constraints:
-
Dependent operations need to be in different stages
-
Some operations can be performed concurrently if they are independent
-
Limited memory: limited number of active variables
Original HalfSipHash Round
Challenge #2: Limited Pipeline Stages
11
HalfSipHash Round Grouped by Dependencies
M =
16
bytes,
c =
2
compression rounds,
d =
4
finalization rounds,
k
=
2
S
i
p
R
o
u
n
d
s
/
p
a
s
s
⇒
p
=
6
p
a
s
s
e
s
Implementing Multiple SipRounds
-
One pipeline pass
-
Ingress+Egress pipelines
-
Recirculation
12
Number of passes required per M-byte input.
-
Ingress-Only:
5
recirculations with
16-byte input
-
Ingress+Egress:
2
recirculations
with 16-byte input
Hardware Resource Utilization
SipID Hardware Prototype
-
Ingress-Only version
-
Implemented in 490 lines
of P4 code
-
Ingress+Egress version
-
Implemented in 779 lines
of P4 code
-
Runs on Barefoot Tofino
Wedge32X-100B
13
Application-Dependent Overhead
-
Iterative processing for each word in
M
-word input
-
Network applications typically require short inputs
-
Acceptable to be below line-rate?
-
Not all ports serve adversarial traffic (e.g., only internet-facing ports)
-
Not all packets need hashing (e.g., only handshake packets)
-
Recirculation ports dedicated for security measures
14
Evaluation
-
Ingress+Egress vs. Ingress-Only: increase maximum hash rate by 3x
-
16 byte input (Ingress + Egress)
-
Approximately 5x speed of single-core CPU
S
i
p
I
D
H
a
s
h
R
a
t
e
w
i
t
h
D
i
f
f
e
r
e
n
t
I
n
p
u
t
L
e
n
g
t
h
s
NetCache (Load-Balancing):
16-byte input
150 million hashes per second
15
Conclusions
-
In-network applications
-
Rely on hashing
-
CRC32 is fast, but insecure
-
Want speed
and
security
-
S
i
p
I
D
:
H
a
l
f
S
i
p
H
a
s
h
i
n
t
h
e
D
a
t
a
P
l
a
n
e
!
-
Open-Source P4 implementation for Tofino
-
https://github.com/Princeton-Cabernet/p4-projects
16
SipHash Tofino
-
Future work
-
Integrating SipID in network applications
Thank you!
Questions?
17
Explore the implementation challenges and opportunities for improved security, privacy, performance, and reliability in data plane applications using (Half)SipHash and CRC32 hashing techniques. Discover the vulnerabilities associated with CRC32 and the need for secure hashing solutions like SipID. Learn about HalfSipHash algorithm and its application in data processing.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
SipID: (Half)SipHash In the Data Plane Secure Keyed Hashing on Programmable Switches Sophia Yoo & Xiaoqi Chen 1
Todays Data Plane Applications - Opportunity for improved - Security - Privacy - Performance - Reliability Implementation Challenges Sophisticated Applications - Hardware Implementation Challenges - Limited Arithmetic Operations - Limited Pipeline Stages 2
Network Applications use Hashing Extensively Indexing Fingerprinting Sampling Hash of header fields used as array index for hash tables (e.g., Jaqen, NetCache) Hash stored in register array as fingerprint of longer flow IDs (e.g., SilkRoad, P4RTT) Pseudo-random hash compared with thresholds to sample a subset of traffic (e.g., AROMA, BeauCoup) 3
CRC32 is widely used in the data plane Significant limitations Efficient - - Not a cryptographic function Insecure as a hash - Computationally inexpensive - Fast Input: 0b11000010 Checksum: 0b00001111 Zero: checksum correct Non-zero: checksum incorrect CRC Verification CRC: Designed to catch accidental bit flips, not intentional changes 4
Vulnerabilities due to CRC32 Indexing Collisions that force table updates and evictions to go to the same index Fingerprinting Collisions that inaccurately group flow IDs together with the same fingerprint Sampling Construct hashes that cause traffic to never be sampled (bypass monitoring) or always sampled (system overload) Always sampled! Never sampled! 5
We need a secure hash, do these exist? - Yes! - But, there are some problems - Computationally expensive - Complex implementation unfriendly to data plane - Inefficient, slow E.g., SHA256, Scrypt, Blowfish - Security Speed SHA256, Scrypt, Blowfish SipID CRC32, Checksum (HalfSipHash in the Data Plane) 6
HalfSipHash-2-4 on an 8-byte (m=2 words) input HalfSipHash-c-d Preprocessing(keys, initial values) v2 v3 Compression Rounds Finalization Rounds v1 v0 m0 Compression Round Compression Round m0 m1 Compression Round Compression Round 0xff m1 Finalization Round Finalization Round Finalization Round Finalization Round One Original HalfSipHash Round 7 Jean-Philippe Aumasson and Daniel J. Bernstein. 2012. SipHash: A Fast Short-Input PRF.
Challenge #1: Limited Arithmetic Operations - Circular Bit Shifts Computationally Expensive! n = 5 a = 0b11010010 a <<< 5 = 0b01011010 Intermediate Steps: x = a << 5 = 0b01000000 y = a >> (8-5) = 0b00011010 b = x OR y = 0b01011010 Strawman circular bit shifting Semantically equivalent slicing 8
Challenge #1: Limited Arithmetic Operations - Circular Bit Shifts Computationally Expensive! n = 5 a = 0b11010010 a <<< 5 = 0b01011010 Intermediate Steps: x = a << 5 = 0b01000000 y = a >> (8-5) = 0b00011010 b = x OR y = 0b01011010 Strawman circular bit shifting Semantically equivalent slicing n = 5 a <<< 5 b[31:0] = a[26:0] ++ a[31:27] 9
Challenge #2: Limited Pipeline Stages Original HalfSipHash Round Constraints: - - - Dependent operations need to be in different stages Some operations can be performed concurrently if they are independent Limited memory: limited number of active variables 10
Challenge #2: Limited Pipeline Stages Original HalfSipHash Round HalfSipHash Round Grouped by Dependencies 11
Implementing Multiple SipRounds - - - One pipeline pass Ingress+Egress pipelines Recirculation - Ingress-Only: 5 recirculations with 16-byte input - Ingress+Egress: 2 recirculations with 16-byte input Number of passes required per M-byte input. M = 16 bytes, c = 2 compression rounds, d = 4 finalization rounds, k = 2 SipRounds/pass p = 6 passes 12
SipID Hardware Prototype - Ingress-Only version - Implemented in 490 lines of P4 code Ingress+Egress version - Implemented in 779 lines of P4 code Runs on Barefoot Tofino Wedge32X-100B - Hardware Resource Utilization - 13
Application-Dependent Overhead - Iterative processing for each word in M-word input - Network applications typically require short inputs Jaqen NetCache SilkRoad P4RTT AROMA BeauCoup 12 bytes 16 bytes 13/37 bytes 16 bytes 13/21 bytes 2~18 bytes - Acceptable to be below line-rate? - Not all ports serve adversarial traffic (e.g., only internet-facing ports) - Not all packets need hashing (e.g., only handshake packets) - Recirculation ports dedicated for security measures 14
Evaluation SipID Hash Rate with Different Input Lengths NetCache (Load-Balancing): 16-byte input 150 million hashes per second - - Ingress+Egress vs. Ingress-Only: increase maximum hash rate by 3x 16 byte input (Ingress + Egress) - Approximately 5x speed of single-core CPU 15
Conclusions - In-network applications - Rely on hashing - CRC32 is fast, but insecure Want speed and security - SipID: HalfSipHash in the Data Plane! Open-Source P4 implementation for Tofino - https://github.com/Princeton-Cabernet/p4-projects - - SipHash Tofino - Future work - Integrating SipID in network applications 16
Thank you! Questions? 17
