1.
Introduction
Chinese Data Security, Inc. (CHNDS) joins the
highly visible effort by the national government in pushing for more
and better Public-Key Infrastructure (PKI) in
CHNDS is sponsoring the TTS Challenge with prize money totally more than US$100,000 (about NT$3.4 million).
2.
Security Estimates
|
Symmetric system (bits) |
ECC key size (bits) |
RSA key size (bits) |
TTS dimension |
Money Prize |
|
56 |
112 |
512 |
(16, 22) |
US$ 1000 |
|
64 |
128 |
768 |
(20, 26) |
US$ 2000 |
|
72 |
144 |
1024 |
(20, 28) |
US$ 4000 |
|
80 |
160 |
1536 |
(24, 32) |
US$ 8000 |
|
88 |
176 |
2048 |
(24, 34) |
US$12000 |
|
96 |
192 |
2560 |
(28, 38) |
US$16000 |
|
112 |
224 |
4096 |
(32, 44) |
US$24000 |
|
128 |
256 |
6144 |
(36, 50) |
US$36000 |
Notes:
1- Please refer to our website for rules to the TTS Challenge.
2- Cryptosystems listed in the same row have similar security.
3- Security estimates for RSA and ECC are taken from a report by EU's NESSIE project (http://www.cryptonessie.org/).
4- Please refer to publicly available documents [7] and [8] for
references to TTS security.
3.
Performance Comparisons
|
Scheme |
ECDSA (163 bits) |
RSA-PSS (1024 bits) |
SFLASH (26, 37) |
TTS (20, 28) |
|
Key set-up |
1.6 ms |
2.7 sec |
1.5 sec |
15.8 ms |
|
Signing |
1.9 ms |
84 ms |
2.8 ms |
0.045 ms |
|
Verifying |
5.1 ms |
2.0 ms |
0.39 ms |
0.25 ms |
|
Signature size |
326 bits |
1024 bits |
259 bits |
224 bits |
|
Public key size |
48 B |
128 B |
15.4 KB |
8.6 KB |
|
Private key size |
24 B |
320 B |
2.4 KB |
1.4 KB |
Notes:
1- ECDSA (ECC signature scheme), ESA-PSS (RSA signature scheme) and
SFLASH are the NESSIE-recommended signature schemes. We excerpted
their performance data from the NESSIE report.
2- We tested everything on a Pentium III/500MHz like NESSIE.
3- TTS, like SFLASH, is a `multivariate' cryptosystem. The two
are similar in principle. All differences arises
from their respective central maps, which leads to a large speed
differential between the two signature schemes.
4.
Performance Report
|
TTS (message size [byte], signature size [byte]) |
Pub. Key (byte) |
Sec. Key (byte) |
Test Platform 1 |
Test Platform 2 |
||||
|
Setup (ms) |
Sign (ms) |
Verify (ms) |
Setup (ms) |
Sign (ms) |
Verify (ms) |
|||
|
(16,22) |
4400 |
879 |
6.2 |
0.028 |
0.13 |
0.9 |
0.004 |
0.01 |
|
(20,26) |
7540 |
1254 |
11.8 |
0.037 |
0.22 |
1.8 |
0.006 |
0.02 |
|
(20,28) |
8680 |
1399 |
15.8 |
0.045 |
0.25 |
2.2 |
0.007 |
0.02 |
|
(24,32) |
13440 |
1864 |
24.0 |
0.057 |
0.38 |
3.7 |
0.009 |
0.03 |
|
(24,34) |
15096 |
2039 |
32.8 |
0.068 |
0.42 |
4.4 |
0.011 |
0.03 |
|
(28,38) |
21812 |
2594 |
48.0 |
0.087 |
0.63 |
7.5 |
0.012 |
0.05 |
|
(32,44) |
33088 |
3444 |
89.0 |
0.110 |
0.94 |
13.2 |
0.017 |
0.07 |
|
(36,50) |
47700 |
4414 |
132 |
0.152 |
1.32 |
21.6 |
0.022 |
0.10 |
Test
Platform 1:
CPU: P3 500MHz; RAM: 384MB;
OS: Win2K server + cygwin
+ gcc 3.2;
ARG: gcc -O3
Test
Platform 2:
CPU: P4 2.4GHz; RAM: 1024MB; OS: Linux + gcc 3.3;
ARG: gcc -O3 -march=pentium4 -fomit-frame-pointer
5. On 8051 Smart Cards
|
Scheme |
Platform |
Clock |
Private Key |
Code Size |
RAM |
Signing Time |
|
TTS (20, 28) |
Intel 8032AH |
3.57 MHz |
1.4KB |
1.5KB |
128B |
198 ms |
|
Intel 8051AH |
1.6KB |
224 ms |
||||
|
Winbond W77E58 |
99 ms |
|||||
|
TTS (24, 32) |
1.5KB |
112 ms |
||||
|
Intel 8051AH |
284 ms |
|||||
|
SFLASH (26, 37) |
2.4KB |
3.3KB |
344B |
1.07 sec |
||
|
Infineon SLE66 |
10 MHz |
59 ms |
||||
|
RSA-1024 |
320B |
N/A |
> 1KB |
many sec |
||
|
NEC mPD789828* |
40 MHz |
100 ms |
||||
|
Infineon SLE66* |
5 MHz |
230 ms |
||||
|
RSA-2048 |
640B |
1.1 sec |
||||
|
ECC-191 |
10 MHz |
24B |
180 ms |
Notes:
1- A
`*' symbol denotes a co-processor (hence costlier implementation)
2- The standard Intel 8051 is called 12T because an instruction cycle
is 12 clock cycles. The Winbond
W77E58 is 4T (hence some 2-3 times faster at the same clock rate), and
the SLE66 part by Siemens-Infineon is said
to be 2T (it really runs via a sixfold
internal clock multiplier), and runs between 4 to 5 times as fast at
the same clock rate.
3- Numbers for ECC, RSA, and SFLASH are taken from the NESSIE report
and a recent paper discussing SFLASH implementation. Numbers for
TTS are excerpted from the paper [9].
4- Current conventional wisdom requires keys to be generated on-card.
TTS both signs and generates keys at high speed without requiring
expensive dedicated crypto hardware. See the following Table.
5- Like most multivariates, TTS has
relatively large public keys. However, due
to its fast key generation, only the private key is needed on
card. With suitable external commands, the smart card can
synthesize the public key in conveniently-sized segments and have it
output block-by-block. This can be done at any time, so the
public key size does not have a negative impact on the memory
requirements of a TTS smart card implementation.
|
Scheme |
Core |
Private Key |
Gen. Time |
Gen. Code |
EEPROM |
|
TTS (20, 28) |
i8032AH |
1399 B |
62 sec |
4.2 KB |
1.2 KB |
|
i8051AH |
|||||
|
W77E58 |
29 sec |
||||
|
TTS (24, 32) |
i8051AH |
1534 B |
170 sec |
1.6 KB |
|
|
W77E58 |
79 sec |
6.
Related Web Sites
[1] Chinese
Data Security Inc., http://www.chnds.com.tw/
[2] New European Schemes for
Signatures, Integrity and Encryption (NESSIE) Project, http://www.cryptonessie.org/
[3] International Association
for Cryptological Research (IACR), http://www.iacr.org/
7. References
[4] NESSIE
Security Report, also can be
found at the NESSIE website [2].
[5] Performance of Optimized
Implementations of the NESSIE Primitives, available at the NESSIE
website [2].
[6] T. Moh,
A Public Key System with Signature
and Master Key Functions,
Communications in Algebra, 27 (1999), pp. 2207-2222.
[7]
J.-M. Chen
and B.-Y. Yang, A More Secure
and Efficacious TTS Signature
Scheme, 6th International Conference on Information Security and
Cryptology (ICISC 2003), Lecture Notes in Computer Science. Also can be
found at IACR e-Print archive [3] http://eprint.iacr.org/2003/160
[8] B.-Y.
Yang and J.-M. Chen, A Study in Security
of Tame-Like Multivariate
Digital Signatures: A New TTS, ACISP 2005
- 10th Australasian Conference on
Information Security and Privacy, Lecture Notes in Computer Science,
Springer-Verlag. Also can be
found at IACR e-Print archive [3] http://eprint.iacr.org/2004/061
[9] B.-Y.
Yang, J.-M. Chen,
and Y.-H. Chen, TTS: High-Speed
Signatures on a
Low-Cost Smart Card, CHES
2004 - Cryptographic
Hardware and Embedded Systems, Lecture Notes in Computer
Science vol. 3156, Springer-Verlag, pp. 371-385.
[10] Akkar, Courtois, Duteuil,
and Goubin, A Fast and Secure
Implementation of SFLASH, PKC 2003, Lecture
Notes in Computer Science vol. 2567, pp. 267-278.
[11] B.-Y.
Yang and J.-M. Chen, All in the XL Family: Thoery and Practice,
ICISC 2004 - 7th International Conference on Information Security and
Cryptology, Lecture Notes in Computer Science
vol. 3506, Springer-Verlag, pp. 67-86.