Re: diffie-hellman subject to an easy brute-force attack?

From: Eric Lee Green (eric_at_badtux.org)
Date: 07/09/03

  • Next message: Security Alert: "SSRT3451 Potential Security Vulnerability in HP-UX network drivers (Data Leakage) (rev. 01)" 
    Date: Tue, 08 Jul 2003 21:59:26 -0700

    srt@nospam.unt.edu wrote:

    > Eric Lee Green <eric@badtux.org> wrote:
    >
    >>> Therefore, there's no way the random (private) "x" values can be
    >>> large, if "g" is large. I suppose that the Diffie-hellman key
    >>> exchange should to happen within fractions of a second -- for this to
    >>> occur, "x" must be very, very small.
    >
    >> No, typically g is very small, for exactly that reason.
    >
    > ???? Why in the world would either g or x have to be small? I can
    > raise a 1024-bit g to a 1024-bit power x, modulo a 1024-bit p, in a
    > matter of milliseconds....

    Oh darn, you're right. I just pulled out good ole' 'dc' and ran it, and
    correlated to GNU MP (which is about 5 times faster than 'dc' at running
    modexp, if I remember right). It's not milliseconds -- it's about half a
    second on my Pentium IV, and about 20 seconds on my Pentium 166 MMX -- but
    it's definitely not 5 minutes. I think the 5 minutes was my attempt at writing
    my own modular exponentiation function in order to bypass having all the code
    bloat of GNU MP around... turns out that fast modular exponentiation is *hard*
    (though in fairness the slowdown came in my multiplication routine, not in the
    modexp function itself, where GNU MP uses Knuth's Algorithm just like I was
    using).
     
    > To the original poster -- x should *not* be small. If your prime
    > modulus p is 1024 bits long, you should use a number that is randomly
    > chosen from the full range 1..p-1 -- which will almost certainly have
    > over 1000 significant bits. And you clearly can't brute-force that...

    Absolutely. I wonder if he's trying to program the DH calculation in Visual
    BASIC? 

    -- 
Eric Lee Green  mailto:eric@badtux.org
Unix/Linux/Storage Software Engineer needs job -- 
see http://badtux.org for resume
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----
  • Next message: Security Alert: "SSRT3451 Potential Security Vulnerability in HP-UX network drivers (Data Leakage) (rev. 01)"
    • Quantcast