Re: Trillian Secure IM
To add to the reference, a preprint is available online at
http://www.dtc.umn.edu/~odlyzko/doc/arch/prime.discrete.logs.pdf
A companion paper that was used crucially in the solution, "Solving
large sparse linear systems over finite fields," pp. 109-133 in
"Advances in Cryptology - CRYPTO '90," A. J. Menezes and S. A. Vanstone
(eds.), Springer Verlag, Lecture Notes in Computer Science #537 (1991)
is available at
http://www.dtc.umn.edu/~odlyzko/doc/arch/sparse.linear.eqs.pdf
Andrew Odlyzko, http://www.dtc.umn.edu/~odlyzko
> On Fri Oct 12, Steve Bellovin wrote:
On Thu, 11 Oct 2007 21:50:06 -0700
Bill Stewart <[EMAIL PROTECTED]> wrote:
>
> > > | Which is by the way exactly the case with SecureIM. How
> > > | hard is it to brute-force 128-bit DH ? My "guesstimate"
> > > | is it's an order of minutes or even seconds, depending
> > > | on CPU resources.
>
> Sun's "Secure NFS" product from the 1980s had 192-bit Diffie-Hellman,
> and a comment in one of the O'Reilly NFS books says that
> "However, by 1990, advances in RISC processors produced
> workstation machines that could, by brute force,
> derive the private key from any public key in under a day."
> but that in 1987 there were still a lot of Motorola 68010 machines
> that took several minutes to generate keys so they didn't want it
> longer. I'm guessing that a 1990 RISC machine was around 50 MIPS,
> so it's maybe 1/100 the speed of a modern single-core CPU.
>
> 128-bit DH sounds like as good a decision as using 40-bit RC4 keys
> would be today.
>
It wasn't just brute force, it was math.
@Article{ nfscrack,
author= {Brian A. LaMacchia and Andrew M. Odlyzko},
journal = {Designs, Codes, and Cryptography},
pages = {46--62},
title = {Computation of Discrete Logarithms in Prime Fields},
volume= {1},
year = {1991},
annote= {Describes how the authors cryptanalyzed Secure RPC.}
}
--Steve Bellovin, http://www.cs.columbia.edu/~smb
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Trillian Secure IM
On Thu, 11 Oct 2007 21:50:06 -0700
Bill Stewart <[EMAIL PROTECTED]> wrote:
>
> > > | Which is by the way exactly the case with SecureIM. How
> > > | hard is it to brute-force 128-bit DH ? My "guesstimate"
> > > | is it's an order of minutes or even seconds, depending
> > > | on CPU resources.
>
> Sun's "Secure NFS" product from the 1980s had 192-bit Diffie-Hellman,
> and a comment in one of the O'Reilly NFS books says that
> "However, by 1990, advances in RISC processors produced
> workstation machines that could, by brute force,
> derive the private key from any public key in under a day."
> but that in 1987 there were still a lot of Motorola 68010 machines
> that took several minutes to generate keys so they didn't want it
> longer. I'm guessing that a 1990 RISC machine was around 50 MIPS,
> so it's maybe 1/100 the speed of a modern single-core CPU.
>
> 128-bit DH sounds like as good a decision as using 40-bit RC4 keys
> would be today.
>
It wasn't just brute force, it was math.
@Article{ nfscrack,
author= {Brian A. LaMacchia and Andrew M. Odlyzko},
journal = {Designs, Codes, and Cryptography},
pages = {46--62},
title = {Computation of Discrete Logarithms in Prime Fields},
volume= {1},
year = {1991},
annote= {Describes how the authors cryptanalyzed Secure RPC.}
}
--Steve Bellovin, http://www.cs.columbia.edu/~smb
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RE: Trillian Secure IM
> | Which is by the way exactly the case with SecureIM. How > | hard is it to brute-force 128-bit DH ? My "guesstimate" > | is it's an order of minutes or even seconds, depending > | on CPU resources. Sun's "Secure NFS" product from the 1980s had 192-bit Diffie-Hellman, and a comment in one of the O'Reilly NFS books says that "However, by 1990, advances in RISC processors produced workstation machines that could, by brute force, derive the private key from any public key in under a day." but that in 1987 there were still a lot of Motorola 68010 machines that took several minutes to generate keys so they didn't want it longer. I'm guessing that a 1990 RISC machine was around 50 MIPS, so it's maybe 1/100 the speed of a modern single-core CPU. 128-bit DH sounds like as good a decision as using 40-bit RC4 keys would be today. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Trillian Secure IM
[EMAIL PROTECTED] wrote: Why bother with all this? There is OTP for gaim, and it works just fine (not to mention it comes from a definitely clueful source). /ji I meant, of course, OTR (off-the-record). And to think that I was using it in another window as I was typing this! Thanks to Scott G. Kelly for pointing this out. /ji - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RE: Trillian Secure IM
> -Original Message- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of Leichter, Jerry > Sent: Monday, October 08, 2007 11:48 AM > To: Alex Pankratov > Cc: cryptography@metzdowd.com > Subject: RE: Trillian Secure IM > > | > But, opportunistic cryptography is even more fun. It is > | > very encouraging to see projects implement cryptography in > | > limited forms. A system that uses a primitive form of > | > encryption is many orders of magnitude more secure than a > | > system that implements none. > | > | Primitive form - maybe, weak form - absolutely not. It > | is actually worse than having no security at all, because > | it tends to create an _illusion_ of protection. > > This is an old argument. I used to make it myself. I even used > to believe it. Unfortunately, it misses the essential truth: > The choice is rarely between really strong cryptography and weak > cryptography; it's between weak cryptography and no cryptography > at all. What this argument assumes is that people really *want* > cryptography; that if you give them nothing, they'll keep on asking > for it; but if you give them something weak, they'll stop asking > and things will end there. But in point of fact hardly anyone > knows enough to actually want cryptography. Those who know enough > will insist on the strong variety whether or not the weak is > available; while the rest will just continue with whatever they > have. Well, I view it from a slightly different perspective. Even the most ignorant person knows a difference between the privacy and the lack of thereof. Cryptography or not. Therefore, if he is being told that A offers a privacy, it may lead this person to assume the level of this privacy protection is adequate ... simply because if it weren't, it wouldn't be offered. Needless to say that this sort of an assumption in case of a weak crypto is dangerous. When there's a choice between no and weak protection, I am of course in favour of latter *if* it is clearly labeled as weak. > | Which is by the way exactly the case with SecureIM. How > | hard is it to brute-force 128-bit DH ? My "guesstimate" > | is it's an order of minutes or even seconds, depending > | on CPU resources. > > It's much better to analyze this in terms of the cost to > the attacker and the defender. Yup, I am familiar with the methodology. My point was that 128bit DH is "breakable" in terms of the people from those forum's threads. Alex - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RE: Trillian Secure IM
> -Original Message- > From: pgut001 [mailto:[EMAIL PROTECTED] > Sent: Monday, October 08, 2007 7:52 PM > To: [EMAIL PROTECTED]; [EMAIL PROTECTED] > Cc: cryptography@metzdowd.com > Subject: Re: Trillian Secure IM > > Marcos el Ruptor <[EMAIL PROTECTED]> writes: > > >I found those threads: > > > >http://forums.ceruleanstudios.com/showthread.php?t=53433 > > > >http://forums.ceruleanstudios.com/showthread.php?t=56207 > > One of them contains a link to an older thread: > > http://www.ceruleanstudios.com/forums/showthread.php?s=&threadid=33279 > > with this gem: > > Speaking as a software developer, if I ever had someone on > my forums who's posts consisted solely of questions about > how my private encryption systems work [an earlier post by > a crypto-savvy person had asked about use of DH primes, the > block cipher encryption mode used, and so on], I would ban > them and report them to their ISP without a second thought. > > If you're interested in creating good encryption, learn the > principles: encryption schemes are weakened when they are based > on someone else's work. So if you're honestly wanting to make > good encryption for Trillian, its a bad idea to try to use CS's > work as a base. Funny enough, his conclusion *is* correct :) Alex - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Trillian Secure IM
Marcos el Ruptor <[EMAIL PROTECTED]> writes: >I found those threads: > >http://forums.ceruleanstudios.com/showthread.php?t=53433 > >http://forums.ceruleanstudios.com/showthread.php?t=56207 One of them contains a link to an older thread: http://www.ceruleanstudios.com/forums/showthread.php?s=&threadid=33279 with this gem: Speaking as a software developer, if I ever had someone on my forums who's posts consisted solely of questions about how my private encryption systems work [an earlier post by a crypto-savvy person had asked about use of DH primes, the block cipher encryption mode used, and so on], I would ban them and report them to their ISP without a second thought. If you're interested in creating good encryption, learn the principles: encryption schemes are weakened when they are based on someone else's work. So if you're honestly wanting to make good encryption for Trillian, its a bad idea to try to use CS's work as a base. Bruce, one for your next Cryptogram? Peter. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Trillian Secure IM
Ian G <[EMAIL PROTECTED]> writes: >Peter Gutmann wrote: >> "Alex Pankratov" <[EMAIL PROTECTED]> writes: >>> SecureIM handshake between two version 3.1 (latest) clients takes about .. >>> 48 >>> bytes. That's altogether, 32 bytes in one direction, and 16 in another. And >>> that's between the clients that have never talked to each other before, so >>> there's no "session resuming" business happenning. >> >> Or they could be using static/ephemeral DH with fixed shared DH key values, >> which isn't much better. (This is just speculation, it's hard to tell >> without >> knowing what the exchanged quantities are). > >Speculation is fun. > >But, opportunistic cryptography is even more fun. It is very encouraging to >see projects implement cryptography in limited forms. A system that uses a >primitive form of encryption is many orders of magnitude more secure than a >system that implements none. Opportunistic cryptography designed as opportunistic cryptography (with key continuity measures and so on) is fun. Opportunistic cryptography that exists because the developers have screwed up something better (and are under the delusion that what they've implemented is something better) is less fun. Peter. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Trillian Secure IM
Why bother with all this? There is OTP for gaim, and it works just fine (not to mention it comes from a definitely clueful source). /ji - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Trillian Secure IM
On Mon, 8 Oct 2007 09:17:48 -0700 "Alex Pankratov" <[EMAIL PROTECTED]> wrote: > > I am actually curious to see what was the DH modulus size in > T's versions that were blocked by AOL. Given T's installation > base, strong SecureIM would've dramatically complicated "lawful > intercepts", which AOL is probably required to implement. > They're not required to decrypt anything unless they're providing the keys. The lawful intercept requirement is to deliver the ciphertext in this case. --Steve Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RE: Trillian Secure IM
| > But, opportunistic cryptography is even more fun. It is | > very encouraging to see projects implement cryptography in | > limited forms. A system that uses a primitive form of | > encryption is many orders of magnitude more secure than a | > system that implements none. | | Primitive form - maybe, weak form - absolutely not. It | is actually worse than having no security at all, because | it tends to create an _illusion_ of protection. This is an old argument. I used to make it myself. I even used to believe it. Unfortunately, it misses the essential truth: The choice is rarely between really strong cryptography and weak cryptography; it's between weak cryptography and no cryptography at all. What this argument assumes is that people really *want* cryptography; that if you give them nothing, they'll keep on asking for it; but if you give them something weak, they'll stop asking and things will end there. But in point of fact hardly anyone knows enough to actually want cryptography. Those who know enough will insist on the strong variety whether or not the weak is available; while the rest will just continue with whatever they have. | Which is by the way exactly the case with SecureIM. How | hard is it to brute-force 128-bit DH ? My "guesstimate" | is it's an order of minutes or even seconds, depending | on CPU resources. It's much better to analyze this in terms of the cost to the attacker and the defender. If the defender assigns relatively low value to his messages, an attack that costs the attacker more than that low value is of no interest. Add in the fact that an attacker may have to break multiple message streams before he gets to one that's worth anything at all. Even something that takes a fraction of a second to decrypt raises the bar considerably for an attacker who just surfs all conversations, scanning for something of interest. It's easy to search for a huge number of keywords - or even much more complex patterns - in parallel at multi-megabyte/second speeds with fgrep-like (Aho-Corasick) algorithms. A little bit of decryption tossed in there changes the calculations completely. I'm not going to defend the design choices here because I have no idea what the protocol constraints were, what the attack model was (or even if anyone actually produced one), what the hardware base was assumed to be at the time this was designed, etc. Perhaps it's just dumb design; perhaps this was the best they could do. Could it be better? Of course. Is it better to not put a front door on your house because the only ones permitted for appearance's sake are wood and can be broken easily? -- Jerry - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RE: Trillian Secure IM
> -Original Message- > From: Marcos el Ruptor [mailto:[EMAIL PROTECTED] > Sent: Monday, October 08, 2007 6:21 AM > To: Alex Pankratov > Cc: cryptography@metzdowd.com > Subject: Re: Trillian Secure IM > > I found those threads: > > http://forums.ceruleanstudios.com/showthread.php?t=53433 > > http://forums.ceruleanstudios.com/showthread.php?t=56207 > > As you can see from the last post in the second thread, ultimately > they agreed that 128-bit DH is secure and that I am just some crazy > guy trying to scare them. Yickes. Ignorance is a bliss. I am actually curious to see what was the DH modulus size in T's versions that were blocked by AOL. Given T's installation base, strong SecureIM would've dramatically complicated "lawful intercepts", which AOL is probably required to implement. Alex - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RE: Trillian Secure IM
> -Original Message- > From: Ian G [mailto:[EMAIL PROTECTED] > Sent: Monday, October 08, 2007 6:05 AM > To: Peter Gutmann > Cc: [EMAIL PROTECTED]; cryptography@metzdowd.com > Subject: Re: Trillian Secure IM > > Peter Gutmann wrote: > > "Alex Pankratov" <[EMAIL PROTECTED]> writes: > > > >> SecureIM handshake between two version 3.1 (latest) > clients takes about .. 48 > >> bytes. That's altogether, 32 bytes in one direction, and > 16 in another. And > >> that's between the clients that have never talked to each > other before, so > >> there's no "session resuming" business happenning. > > > > Or they could be using static/ephemeral DH with fixed > shared DH key values, > > which isn't much better. (This is just speculation, it's > hard to tell without > > knowing what the exchanged quantities are). > > > Speculation is fun. > > But, opportunistic cryptography is even more fun. It is > very encouraging to see projects implement cryptography in > limited forms. A system that uses a primitive form of > encryption is many orders of magnitude more secure than a > system that implements none. Primitive form - maybe, weak form - absolutely not. It is actually worse than having no security at all, because it tends to create an _illusion_ of protection. Which is by the way exactly the case with SecureIM. How hard is it to brute-force 128-bit DH ? My "guesstimate" is it's an order of minutes or even seconds, depending on CPU resources. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Trillian Secure IM
Marcos el Ruptor wrote: If that's DH exchange, then it's 128 bit one. Fertile ground for some interesting speculation, don't you think ? There is no speculation. It is 128-bit DH. I have reported over three years ago to the Trillian forum that they are using 128-bit DH and that it is not secure. You can look up my messages about it and how much I got abused for it by everyone trying to explain to me that 1) it IS secure and 2) no one cares anyway. They did not change it since then although they promised to. Had a look, but it seems to me they said they wouldn't fix it unless there was an actual, active exploit for it, and my guess would be even then they would just make cosmetic changes to stop that particular instance of an exploit from working.. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Trillian Secure IM
I found those threads: http://forums.ceruleanstudios.com/showthread.php?t=53433 http://forums.ceruleanstudios.com/showthread.php?t=56207 As you can see from the last post in the second thread, ultimately they agreed that 128-bit DH is secure and that I am just some crazy guy trying to scare them. Ruptor - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Trillian Secure IM
If that's DH exchange, then it's 128 bit one. Fertile ground for some interesting speculation, don't you think ? There is no speculation. It is 128-bit DH. I have reported over three years ago to the Trillian forum that they are using 128-bit DH and that it is not secure. You can look up my messages about it and how much I got abused for it by everyone trying to explain to me that 1) it IS secure and 2) no one cares anyway. They did not change it since then although they promised to. I'd also made an open-source replacement DLL back then with 512-bit ECDH, which also supported their 128-bit DH clients if they initiated secure communication first, but it may have some compatibility issues with later versions of Trillian. It's supposed to display the common key fingerprint, not sure if it works now. Feel free to correct it and to improve it, but Cerulean Studios won't pay for it. It's still on http://cryptolib.com/ruptor/ Marcos el Ruptor PS: There was also a buffer overflow in their original DLL if you send a very long key. I don't know if they have fixed it or not. I haven't used Trillian since I bought a Mac. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Trillian Secure IM
"Alex Pankratov" <[EMAIL PROTECTED]> writes: >SecureIM handshake between two version 3.1 (latest) clients takes about .. 48 >bytes. That's altogether, 32 bytes in one direction, and 16 in another. And >that's between the clients that have never talked to each other before, so >there's no "session resuming" business happenning. Or they could be using static/ephemeral DH with fixed shared DH key values, which isn't much better. (This is just speculation, it's hard to tell without knowing what the exchanged quantities are). Peter. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Trillian Secure IM
Hi, I've been poking around Oscar (ICQ/AIM) protocol parsing and had a look at Trillian's SecureIM handshake protocol. For those who don't know, Trillian is a very popular multi- protocol instant messanging application for Windows. One of its notable features, for which is got some rave/positive reviews, is an ability to encrypt ICQ/AIM IMs exchanged by two Trillian instances. AOL made repeated attempts to block SecureIM, but eventually stopped them [1]. The protocol is closed, but it was reversed engineered by some guys over at GAIM project. It appeared to be a Blowfish encryption of bulk IMs using a key derived from an anonymous DH exchange [2]. This was also indirectly confirmed by another project [3]. Leaving aside the lack of authentication and replay protection, here's what is even more striking - SecureIM handshake between two version 3.1 (latest) clients takes about .. 48 bytes. That's altogether, 32 bytes in one direction, and 16 in another. And that's between the clients that have never talked to each other before, so there's no "session resuming" business happenning. If that's DH exchange, then it's 128 bit one. Fertile ground for some interesting speculation, don't you think ? Alex [1] http://en.wikipedia.org/wiki/Trillian_%28instant_messenger%29#Entry_into_mai nstream_and_the_.22IM_Wars.22 [2] http://sourceforge.net/tracker/download.php?group_id=235&atid=300235&file_id =56799&aid=777300 [3] http://code.google.com/p/joscar/wiki/TrillianSecureIm - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
