Re: what should "k-bit security" mean?

From: Tom St Denis (tomstdenis_at_iahu.ca)
Date: 08/29/03 

Date: Fri, 29 Aug 2003 12:36:08 GMT

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

William Whyte wrote:
| djohn37050@aol.com (DJohn37050) wrote in message
news:<20030828163438.18170.00000098@mb-m24.aol.com>...
|
|>NIST is their Jan 03 Key Management Guideline says: Cryptographic
algorithms
|>provide different “strengths” of security, depending on the
algorithm
|>and the key size used.
|
| [...]
|
|>An algorithm that provides X bits of strength would, on average, take
2X-1T to
|>attack, where T is the
|>amount of time that is required to perform one encryption of a
plaintext value
|>and comparison of
|>the result against the corresponding ciphertext value.
|
|
| Right. And this is the measure that we used in the NTRU paper
| referenced by Wei in his first post
| (http://www.ntru.com/cryptolab/pdf/NTRUTech012v2.pdf).
| (Presume the original text read "2<sup>X</sup>" rather than "2X", btw.)
|
| The argument is that this measure is slightly misleading in the case of
| NTRU, because some keys take so much less time than others to attack
| that an attacker can concentrate on those keys. For example, with
NTRU, the
| paper referenced shows that for N=110, one key in 10 (Wei previously
| said 12 -- sorry, that was my fault) takes 1/100 as long to break as
| the average. Say the average breaking time is T; the attacker can simply
| take 10 keys, try to break each one for time T/100, and if the timer runs
| out move onto the next key. This will let him recover a single key in time
| about T/10.

If that is the case they really should have divided the work effort by
ten [worst case on average].

That being said [shooting from hip] I don't think you can just say "I'll
run this attack for exactly X time and move on if it didn't work".
Remember all these times are estimates and not deterministic.

Tom
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQE/T0i5sP+tEsHHY0ARAo2FAJ9+h6IsHoHJtgwYqUJ7FjWRMMV/tgCeKGBC
lojVk79nCoEGN/BPxTbuZzM=
=Zlcv
-----END PGP SIGNATURE-----

Relevant Pages

  • Re: what should "k-bit security" mean?
    ... What is the time t of an attack? ... algorithm to end of execution of the algorithm. ... Suppose the problem is inverting SHA1. ...
    (sci.crypt)
  • Re: Quantum slip - Quantum conspiracy
    ... RSA and DH are done in by Shor's algorithm. ... So you can look on ECC as slightly more vulnerable ... As far as NTRU goes, ...
    (sci.crypt)
  • Re: Simple block cypher for 8-bit microcontrollers
    ... I do have specific applications in mind, but until I can be sure that the algorithm is correct, I'll be using other well known algorithms in my specific applications;) ... block ciphers. ... There are many variations on the basic slide attack. ...
    (sci.crypt)
  • Re: Algorithm Strength Scale
    ... therefore rendering it useless for serious purposes. ... It is arguable that this delivers an equivalent key in an equivalent algorithm, but it certainly does not recover the "functional key" of the original algorithm, and may not necessarily be possible to convert to the key itself. ... Admittedly, this is a significantly unusual form of attack, but it certainly violates the statement that there are "only ... ... It has no relation to reality, only serves to provide an appearance of thoughtfulness. ...
    (sci.crypt)
  • Re: [Full-Disclosure] IDS Signatures
    ... do take a look at snort. ... firewall, so that when snort sees as attack, i ... >> a database of intrusion signatures using MySQL database. ... >> algorithm be appropriate for pattern matching in IDS?) ...
    (Full-Disclosure)