Re: Feedback from the LibTomMath Book?
[Originally I was going to make this a private reply but since I have a
cool explanation of Karatsuba I'll share it with the group]
--- Anton Stiglic [EMAIL PROTECTED] wrote:
I think it looks pretty good!.
Here are some comments:
On page 82 you mention Fourier Transform based solutions, but
don't describe any later on. It would be nice if you did.
Two problems
1. I don't fully understand the FFT based solutions
2. I personally don't see the need for FFT in common day algorithms.
Heck even Toom-Cook won't kick in until the numbers are very large.
Recently I needed a fast Square-root routine, and found that not many
libraries have one (OpenSSL has a mod square but not a
straightforward
square root function, GMP has a square-root but it doesn't seem to be
fast,
bc is faster than GMP for that...).
If you could write something about that it would be nice. I think
Karatsuba
square root is good for that:
http://www.inria.fr/rrrt/rr-3805.html
Oddly enough, Zimmermann implemented this in GMP but I don't know why
it's slow...
I do include a Newton based root function which is fairly fast [haven't
timed it against others]. I'll look into others.
In section 6.2.4, equation 6.6., you wrote:
f(x)*g(x) = acx^2 + ((a -b)(c-d) + ac + bd)x + bd
That doesn't seem to work, since it gives
acx^2 + a(c-d)x - b(c-d)x + acx + bdx + bd
= acx^2 +acx -adx -bcx +bdx +acx + bdx +bd
= acx^2 +2acx +2bdx -adx -bcx +bc
Examine the terms.
ac = W(oo) = 1W_2 + 0W_1 + 0W_0
bd = W(0) = 0W_2 + 0W_1 + 1W_0
The middle term
(a - b)(c - d)
can be written as
(a_1 - a_0)(b_1 - b_0) = (-a(-1))(-b(-1)) = -\Zeta_{-1}
Where a(x) = a_1*x + a_0 [same for b(x)]
So -a(-1) == -(a_1 * -1 + a_0) == a_1 - a_0
This would give where W(x) == w_2 * x^2 + w_1 * x + w_0
-W(-1) = (-a(-1))(-b(1)) = -(w_2 * 1 + w_1 * -1 + w_0) = -w_2 + w_1
-w_0
Which combined gives you the matrix
W(0) = 0 0 1
-W(-1) = -1 1 -1
W(oo) = 1 0 0
This means adding the two terms gives you the middle w_1 term. Hence
the polynomial is actually correct.
Alternatively you can use W(1) = w_2 + w_1 + w_0 = a(1)b(1) and
subtract the first and third row from the middle.
On the primality test section, maybe you should not that the
Miller-Rabin test doesn't have any candidates that will
pass the test for all bases (such as Carmichael numbers for
the Fermat test). You should also talk about the probabilities,
HAC, see in particular note 4.47 so as not to make the same
mistake that allot of people make... You should understand
that note very well.
Will do. I wanted to get the book out the door quick so I just
finished the pseudo code ...
Continue the good work!
Thanks,
Tom
__
Do you Yahoo!?
SBC Yahoo! DSL - Now only $29.95 per month!
http://sbc.yahoo.com
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Draft Edition of LibTomMath book
Werner Koch [EMAIL PROTECTED] writes: Does the proprietary SSH still use GMP? I know no other major crypto apps using GMP for big number math. I've seen it used in a couple of lesser-known apps that I played with for interop testing, nothing that counts as a major app though. Maybe it's being used by people who prefer the LGPL to the more widely-used OpenSSL bignum lib's BSD license (or perhaps it's the fact that GMP has documentation :-). A problem with GMP is that it heavily uses alloca() and thus it is not that hard to find traces of secrets in the core. Ouch! This is a pity, because GMP seems to have the most active development in terms of both algorithm optimisation and machine-specific optimisations - if you want to find a version that runs well on $obscure_embedded_platform, it's pretty much GMP or nothing. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Apple DRM Revisited
http://www.scifihifi.com/weblog/mac/AppleDRMRevisited.html Sci-Fi Hi-Fi: Weblog Sat, 17 May 2003 Apple DRM Revisited Posted: 20:54 | Category: [ /mac ] | Permanent Link: # In a previous post detailing my research into the iTunes Music Store's digital rights management scheme, I promised to continue hacking away at the problem and post updates on my progress. In keeping with that promise, here is an account of my recent hacktivities. The first thing I should mention is that Phil Schillermania Schiller recently gave an interview to BusinessWeek wherein he, for the first time, publicly names the ITMS's DRM scheme. It turns out that Apple is using a system called FairPlay , which was evidently developed by a company called VeriDisc. Schiller, in keeping with Apple's silence on DRM matters so far, is extremely cagey about discussing the true nature of the protection. When asked Is there any DRM built into the downloads themselves or is it all in iTunes 4, Schiller responds: No, it's all built into the [iTunes] system. Our goal is to make it transparent for the user so that they never have to think about DRM. We're using a DRM technology under the hood called FairPlay. It's a DRM technology used by iTunes and QuickTime at the system level. To which I respond: lies ! This is obviously false-if the downloaded files didn't contain any DRM information you would be able to copy the same file from computer to computer and iTunes would be none the wiser. Readers who saw my earlier post may remember that I closed with a bit of speculation as to which part of the AAC file actually contains this DRM information: the 'drms' atom. The atom name itself strongly suggests this, and a quick comparison of the relative structure of protected and unprotected AAC files seems to reinforce the idea (note that the only obvious difference between the two is that the protected file contains a 'drms' atom in place of the unprotected file's 'mp4a'). This, then, brings to mind an obvious question: would removing the 'drms' atom and replacing it with an 'mp4a' atom effectively remove the DRM protection? To find out, I began reworking my original AAC parsing code so that it could read an entire atom structure into an object hierarchy, modify it, and then write the whole thing back out to disk. It took awhile to get my code to the point where it could produce files that didn't crash QuickTime, so you can imagine my elation when I finally managed to generate a valid, unprotected AAC file (as confirmed by QuickTime's movie info window). The original, protected AAC An AAC output by my code Unfortunately, my elation evaporated as soon as I actually tried to play the file, only to encounter silence. That is, QuickTime had the length and all of the file properties (sample rate and so forth) correct, and would begin playing the file normally-it just wouldn't produce any audio. Further research suggested that I probably needed to preserve the elementary stream descriptor atom, which always seems to be embedded within the 'drms' or 'mp4a' atom. With this in mind, I rewrote my code so that it preserves the file's 'esds' atom within the substituted 'mp4a'. Unfortunately, the results are the same-silence. So, I seem to have reached an impasse. I have produced some pretty nice code for parsing QuickTime-like files, but I really need to take a break from my hacking efforts to get some much needed rest and work on other projects, so I've decided to publish my latest code and shelf the project (at least for now). It can be downloaded (as usual) as a Project Builder project: -AACExperiments2.dmg Once again, I ask anyone who makes progress based on this code to keep me informed. I would be particularly interested to hear from someone who might be able to bring a better understanding of MPEG-4 to bear on the problem (this project has definitely put learn more about MPEG on my To Do list!). [0 trackbacks ] [ 8 comments ] -- - R. A. Hettinga mailto: [EMAIL PROTECTED] The Internet Bearer Underwriting Corporation http://www.ibuc.com/ 44 Farquhar Street, Boston, MA 02131 USA ... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience. -- Edward Gibbon, 'Decline and Fall of the Roman Empire' - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Attacking networks using DHCP, DNS - probably kills DNSSEC
Somebody did an interesting attack on a cable network's customers. They cracked the cable company's DHCP server, got it to provide a Connection-specific DNS suffic pointing to a machine they owned, and also told it to use their DNS server. This meant that when your machine wanted to look up yahoo.com, it would look up yahoo.com.attackersdomain.com instead. This looks like it has the ability to work around DNSSEC. Somebody trying to verify that they'd correctly reached yahoo.com would instead verify that they'd correctly reached yahoo.com.attackersdomain.com, which can provide all the signatures it needs to make this convincing. So if you're depending on DNSSEC to secure your IPSEC connection, do make sure your DNS server doesn't have a suffix of echelon.nsa.gov... -- RISKS-LIST: Risks-Forum Digest Saturday 17 June 2003 Volume 22 : Issue 78 http://catless.ncl.ac.uk/Risks/22.78.html -- Date: Fri, 20 Jun 2003 15:33:15 -0400 From: Tom Van Vleck [EMAIL PROTECTED] Subject: ISP's DHCP servers infiltrated http://ask.slashdot.org/article.pl?sid=03/06/19/2325235mode=threadtid=126tid=172tid=95 ... It turns out, Charter Communications' DHCP servers were infiltrated and were providing p5115.tdko.com as the 'Connection-specific DNS suffix', causing all non-hardened Windows (whatever that means in a Windows context) machines to get lookups from a hijacked subdomain DNS server which simply responded to every query with a set of 3 addresses (66.220.17.45, 66.220.17.46, 66.220.17.47). On these IPs were some phantom services. There were proxying Web servers (presumably collecting cookies and username/password combos), as well as an ssh server where the perpetrators were most likely hoping people would simply say 'yes' to the key differences and enter in their username/password... Hmm, my cable ISP was down this morning. Maybe coincidence. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Attacking networks using DHCP, DNS - probably kills DNSSEC
On Sat, Jun 28, 2003 at 01:06:03PM -0700, Bill Stewart wrote: Somebody did an interesting attack on a cable network's customers. They cracked the cable company's DHCP server, got it to provide a Connection-specific DNS suffic pointing to a machine they owned, and also told it to use their DNS server. This meant that when your machine wanted to look up yahoo.com, it would look up yahoo.com.attackersdomain.com instead. This problem is old and well-understood. It is why there is work in the IETF to combine the acquisition of a DHCP lease with the acquisition of an initial IPsec SA to integrity-protect that lease. It's not easy for me to see why anyone would expect anything *but* that MITM attacks against client systems that are entirely configured by DHCP would be practical. If the DHCP client and server share no cryptographic guarantee of trust... ..oh, I'm sorry, I forgot that the anacephalic have fallen for you can magic up trust out of nowhere about ten times in succession in my immediately previous area of work, 802.11. :-) Where I used to work, at ReefEdge, we disposed of the 802.11 security garbage and used a TLS-based solution that was not entirely unlike PIC, dispensing temporary credentials for use with IKE to users based on their legacy authentication. As the designer and maintainer of this system, I became *very* cognizant of DHCP-based and DNS-based attacks, and very skeptical of the sort of proposal someone brought be every few days suggesting that some later establishment of a trust relationship could overcome a successful MITM attack on one of the early stages of the client's boot up and get SA negotiation. (of course, I also became very skeptical of many other folks' use legacy credentials to bootstrap IKE techniques; there are implementations out there in widespread use which default to only authentication methods that are trivially MITMed, and at least one I can think of that _can not be configured_ to do standard IKE in a secure way. Ouch! But the simultaneous IKE and DHCP proposal I read a few years ago at the London IETF seemed pretty sound.) Thor - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
