[30519] in bugtraq
Re: Algorimic Complexity Attacks
daemon@ATHENA.MIT.EDU (=?ISO-8859-1?Q?G=F6tz_Babin-Ebell?)
Tue Jun 24 19:19:16 2003
Message-ID: <3EF89C64.7060200@trustcenter.de>
Date: Tue, 24 Jun 2003 20:45:56 +0200
From: =?ISO-8859-1?Q?G=F6tz_Babin-Ebell?= <babin-ebell@trustcenter.de>
MIME-Version: 1.0
To: Nicholas Weaver <nweaver@CS.berkeley.edu>
In-Reply-To: <20030608102235.B12903@ring.CS.Berkeley.EDU>
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=sha1; boundary="------------ms020009050209020402010807"
--------------ms020009050209020402010807
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
Hello Nicolas
Nicholas Weaver wrote:
> On Sun, Jun 08, 2003 at 06:17:38PM +0200, Pavel Kankovsky composed:
>
>>We need a function having a (relatively) small set of results in order to
>>build a hash table. We can also assume the information about collisions
>>leaks out via a timing channel. Ergo, a persistent attacker can find
>>enough collisions by trial and error.
>
> IF the hash is good, FINDING collisions doesn't necessarily help the
> attacker, as the attacker really needs to generate lots of collisions
> to make the searches O(n) instead of O(1), since that is teh key
> behind this attack.
You could do some improvement if you store the collisions
not in a list, but in a new hash table.
In that 2nd hash table you add a salt.
So the attacker must find many sets of data that result not only
in a collistion, but additional result in collisions in the
2nd hash table.
If the salt is some on the spot generated random data,
that should be nearly impossible...
Generating the 2nd hash table only if there at least n collissions
should keep the load on the system low...
Bye
Goetz
--
Goetz Babin-Ebell, TC TrustCenter AG, http://www.trustcenter.de
Sonninstr. 24-28, 20097 Hamburg, Germany
Tel.: +49-(0)40 80 80 26 -0, Fax: +49-(0)40 80 80 26 -126
--------------ms020009050209020402010807
Content-Type: application/x-pkcs7-signature; name="smime.p7s"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="smime.p7s"
Content-Description: S/MIME Cryptographic Signature
MIAGCSqGSIb3DQEHAqCAMIACAQExCzAJBgUrDgMCGgUAMIAGCSqGSIb3DQEHAQAAoIIIkDCC
BEQwggOtoAMCAQICDwCQHgAAAAJOQu0jEgf3pTANBgkqhkiG9w0BAQUFADCBvDELMAkGA1UE
BhMCREUxEDAOBgNVBAgTB0hhbWJ1cmcxEDAOBgNVBAcTB0hhbWJ1cmcxOjA4BgNVBAoTMVRD
IFRydXN0Q2VudGVyIGZvciBTZWN1cml0eSBpbiBEYXRhIE5ldHdvcmtzIEdtYkgxIjAgBgNV
BAsTGVRDIFRydXN0Q2VudGVyIENsYXNzIDMgQ0ExKTAnBgkqhkiG9w0BCQEWGmNlcnRpZmlj
YXRlQHRydXN0Y2VudGVyLmRlMB4XDTAzMDIxMDE0NDI1MFoXDTA0MDIxMDE0NDI1MFowgaox
CzAJBgNVBAYTAkRFMRAwDgYDVQQIEwdIYW1idXJnMRAwDgYDVQQHEwdIYW1idXJnMRowGAYD
VQQKExFUQyBUcnVzdENlbnRlciBBRzEUMBIGA1UECxMLRW50d2lja2x1bmcxGjAYBgNVBAMT
EUdvZXR6IEJhYmluLUViZWxsMSkwJwYJKoZIhvcNAQkBFhpiYWJpbi1lYmVsbEB0cnVzdGNl
bnRlci5kZTCCASIwDQYJKoZIhvcNAQEBBQADggEPADCCAQoCggEBALB6adN6EChrpAbT5KV1
ceRRIDAoGnz2gsBoFI2BwJLS+RpuIZfdJOepm4crg3X6LXrMKwSF/lshFeHrVPtLzabgLGyF
SujsJP0z3u7f4XNYCGHl4UbyPkYboIP9GC/DRtsknO1YfJUy/4yKBG4VjJ4AP6vZTEQey6jm
xelsK2ek4vwRfUjs/z9UcZmtj4ipiHP6IqFyydDTLarn1jWHUu2zFnJzryZ6mXdOUPihCOFG
D+c1KFksZ1VscgDpKygTQcIg/VItmbeFkhOj9IkboOyiVKvvfhujlxmdm9ACt22MjMrB0RAb
9TR1DgXlyofwykKAK+GM8Cu8jcKaJjvfhaMCAwEAAaOB0zCB0DAMBgNVHRMBAf8EAjAAMA4G
A1UdDwEB/wQEAwIF4DA+BglghkgBhvhCAQgEMRYvaHR0cDovL3d3dy50cnVzdGNlbnRlci5k
ZS9ndWlkZWxpbmVzL2luZGV4Lmh0bWwwEQYJYIZIAYb4QgEBBAQDAgWgMF0GCWCGSAGG+EIB
AwRQFk5odHRwczovL3d3dy50cnVzdGNlbnRlci5kZS9jZ2ktYmluL2NoZWNrLXJldi5jZ2kv
OTAxRTAwMDAwMDAyNEU0MkVEMjMxMjA3RjdBNT8wDQYJKoZIhvcNAQEFBQADgYEAObOwuCFG
0HmVvCm8llpJ3qsBqtZgFyUT0wuz8JG6CZjHn5lwvOg+8m8huKrE5oGEQIo9EwLcFLDNVsxB
CiwjX2juU3JQl2Hs2smUyHkOqg+W0COetRp+PcDAk4hk0Mth5A3bDy3FrzyhbjpYjAZTvnsY
9+QYmJm5cGWBJK9I7kIwggREMIIDraADAgECAg8AkB4AAAACTkLtIxIH96UwDQYJKoZIhvcN
AQEFBQAwgbwxCzAJBgNVBAYTAkRFMRAwDgYDVQQIEwdIYW1idXJnMRAwDgYDVQQHEwdIYW1i
dXJnMTowOAYDVQQKEzFUQyBUcnVzdENlbnRlciBmb3IgU2VjdXJpdHkgaW4gRGF0YSBOZXR3
b3JrcyBHbWJIMSIwIAYDVQQLExlUQyBUcnVzdENlbnRlciBDbGFzcyAzIENBMSkwJwYJKoZI
hvcNAQkBFhpjZXJ0aWZpY2F0ZUB0cnVzdGNlbnRlci5kZTAeFw0wMzAyMTAxNDQyNTBaFw0w
NDAyMTAxNDQyNTBaMIGqMQswCQYDVQQGEwJERTEQMA4GA1UECBMHSGFtYnVyZzEQMA4GA1UE
BxMHSGFtYnVyZzEaMBgGA1UEChMRVEMgVHJ1c3RDZW50ZXIgQUcxFDASBgNVBAsTC0VudHdp
Y2tsdW5nMRowGAYDVQQDExFHb2V0eiBCYWJpbi1FYmVsbDEpMCcGCSqGSIb3DQEJARYaYmFi
aW4tZWJlbGxAdHJ1c3RjZW50ZXIuZGUwggEiMA0GCSqGSIb3DQEBAQUAA4IBDwAwggEKAoIB
AQCwemnTehAoa6QG0+SldXHkUSAwKBp89oLAaBSNgcCS0vkabiGX3STnqZuHK4N1+i16zCsE
hf5bIRXh61T7S82m4CxshUro7CT9M97u3+FzWAhh5eFG8j5GG6CD/Rgvw0bbJJztWHyVMv+M
igRuFYyeAD+r2UxEHsuo5sXpbCtnpOL8EX1I7P8/VHGZrY+IqYhz+iKhcsnQ0y2q59Y1h1Lt
sxZyc68mepl3TlD4oQjhRg/nNShZLGdVbHIA6SsoE0HCIP1SLZm3hZITo/SJG6DsolSr734b
o5cZnZvQArdtjIzKwdEQG/U0dQ4F5cqH8MpCgCvhjPArvI3CmiY734WjAgMBAAGjgdMwgdAw
DAYDVR0TAQH/BAIwADAOBgNVHQ8BAf8EBAMCBeAwPgYJYIZIAYb4QgEIBDEWL2h0dHA6Ly93
d3cudHJ1c3RjZW50ZXIuZGUvZ3VpZGVsaW5lcy9pbmRleC5odG1sMBEGCWCGSAGG+EIBAQQE
AwIFoDBdBglghkgBhvhCAQMEUBZOaHR0cHM6Ly93d3cudHJ1c3RjZW50ZXIuZGUvY2dpLWJp
bi9jaGVjay1yZXYuY2dpLzkwMUUwMDAwMDAwMjRFNDJFRDIzMTIwN0Y3QTU/MA0GCSqGSIb3
DQEBBQUAA4GBADmzsLghRtB5lbwpvJZaSd6rAarWYBclE9MLs/CRugmYx5+ZcLzoPvJvIbiq
xOaBhECKPRMC3BSwzVbMQQosI19o7lNyUJdh7NrJlMh5DqoPltAjnrUafj3AwJOIZNDLYeQN
2w8txa88oW46WIwGU757GPfkGJiZuXBlgSSvSO5CMYIEdzCCBHMCAQEwgdAwgbwxCzAJBgNV
BAYTAkRFMRAwDgYDVQQIEwdIYW1idXJnMRAwDgYDVQQHEwdIYW1idXJnMTowOAYDVQQKEzFU
QyBUcnVzdENlbnRlciBmb3IgU2VjdXJpdHkgaW4gRGF0YSBOZXR3b3JrcyBHbWJIMSIwIAYD
VQQLExlUQyBUcnVzdENlbnRlciBDbGFzcyAzIENBMSkwJwYJKoZIhvcNAQkBFhpjZXJ0aWZp
Y2F0ZUB0cnVzdGNlbnRlci5kZQIPAJAeAAAAAk5C7SMSB/elMAkGBSsOAwIaBQCgggJ7MBgG
CSqGSIb3DQEJAzELBgkqhkiG9w0BBwEwHAYJKoZIhvcNAQkFMQ8XDTAzMDYyNDE4NDU1Nlow
IwYJKoZIhvcNAQkEMRYEFIEL8FB6LM3xWfxekIpBq2FojPR8MFIGCSqGSIb3DQEJDzFFMEMw
CgYIKoZIhvcNAwcwDgYIKoZIhvcNAwICAgCAMA0GCCqGSIb3DQMCAgFAMAcGBSsOAwIHMA0G
CCqGSIb3DQMCAgEoMIHhBgkrBgEEAYI3EAQxgdMwgdAwgbwxCzAJBgNVBAYTAkRFMRAwDgYD
VQQIEwdIYW1idXJnMRAwDgYDVQQHEwdIYW1idXJnMTowOAYDVQQKEzFUQyBUcnVzdENlbnRl
ciBmb3IgU2VjdXJpdHkgaW4gRGF0YSBOZXR3b3JrcyBHbWJIMSIwIAYDVQQLExlUQyBUcnVz
dENlbnRlciBDbGFzcyAzIENBMSkwJwYJKoZIhvcNAQkBFhpjZXJ0aWZpY2F0ZUB0cnVzdGNl
bnRlci5kZQIPAJAeAAAAAk5C7SMSB/elMIHjBgsqhkiG9w0BCRACCzGB06CB0DCBvDELMAkG
A1UEBhMCREUxEDAOBgNVBAgTB0hhbWJ1cmcxEDAOBgNVBAcTB0hhbWJ1cmcxOjA4BgNVBAoT
MVRDIFRydXN0Q2VudGVyIGZvciBTZWN1cml0eSBpbiBEYXRhIE5ldHdvcmtzIEdtYkgxIjAg
BgNVBAsTGVRDIFRydXN0Q2VudGVyIENsYXNzIDMgQ0ExKTAnBgkqhkiG9w0BCQEWGmNlcnRp
ZmljYXRlQHRydXN0Y2VudGVyLmRlAg8AkB4AAAACTkLtIxIH96UwDQYJKoZIhvcNAQEBBQAE
ggEAivkI5ifR09rHfaLnwBamHW4JB+wnPNKRvtFm37rcgQyuPFCv3Cw1WEnFV9XFWntlckZ+
K9I9/QoKjN78liuTkRzgHmbj/ITUd9Qbwyy7fDrk9P+vbFyDcMGNFl+vhnC7fU/At0NKaV1s
DqbwwxMAQbC6lJCGRsa6UV9reKaREhHd/EjMLxhRIQnVQ0OQsOe+RaaAF5rgNqhkJStHWrIg
rVSCgWT7Eot6r1uTJlpzHxyXc6EgRgWhnjFuzpQNpFiDdQex1GLV0VKuslobRWBve5U1DbFR
xBmEVsO435f1bsgj7EomPJNHdTWFj6sUahojt2xYcg8PTPcVH+r6kFobWwAAAAAAAA==
--------------ms020009050209020402010807--
