[Beowulf] Re: "hobbyists"

Robert G. Brown rgb at phy.duke.edu
Thu Jun 19 07:26:45 PDT 2008

On Thu, 19 Jun 2008, Vincent Diepeveen wrote:

> USA and allowing encryption beyond the cracking capabilities of a 1st year 
> computer science student... ...hmmm

Dear Vincent,

IIRC almost any of the high-end encryption routines available within
linux are effectively uncrackable, certainly uncrackable to somebody
with less than NSA-class resources.  Most of the routines scale -- if
1024 bit keys still leave you worried, use a larger one.  Brute force
searches of keyspace are easily driven past the capabilities of any
computer; all that remains are solving certain "hard" problems in e.g.
number theory implicit to the method.  I haven't looked at the
literature recently, but to the best of my knowledge e.g the integer
factorization problem cannot be solved in polynomial time for any known
algorithm, and factoring a single 663 bit integer in a test that took
ballpark of a GFLOP-century of effort for the record as of 2005.  NP
means that a 2048 bit key would very likely require TFLOP-centuries of
effort if not more -- maybe NSA trying really really hard could do it,
maybe IBM using big blue could do it, maybe the top ten of the top-500
could do it -- in a year or ten of unbroken effort -- or maybe not.

Moore's Law and the possible advent of quantum computing (where there is
reportedly a P-time algorithm but no hardware to run it on) might change
this, a truly significant advance in number theory or human cleverness
might change it -- training a humongous neural network to perform 2048
bit factorizations well enough that its partial and horrendously
parallel and nonlinear solutions serve to reduce the search space to
where NP searches can find it in human-accessible time, for example.
Barring that, you're pretty safe with any of the open source encryption
methods with a large key.


> I remember how i did do big efforts to get vista ultimate bitlocker to work.
> On paper it sounds ok. AES 256 bits CBC.

AES is a "good" encryption IIRC.  The weakness, of course, is guarding
the key (as always).  ssh is quite secure, but not if you have both of
my public/private keys.  Symmetric methods are quite secure as well, but
not if someone takes your key.  And on Vista, it doesn't matter whether
or not the key is on a USB stick if somebody cracks the OS, which is the
REAL weak link in the chain, and inserts code to copy your key the next
time you insert the USB stick and then decrypt and transmit the entire
contents of your encrypted drive.

It takes NSA resources, perhaps, to find long keys or factor long keys
or solve elliptical or discrete logarithm problems in number theory that
have only NP algorithms that scale badly as the keysize gets large.
Does anyone seriously think that it takes NSA resources to crack Vista
itself?  Especially in a consumer environment (that is, systems run by
anyone less knowledgeable than a computer systems engineer or sysadmin)?


> The idea is : your usb stick has the encryption key and only that thing has 
> it.
> So no one can decrypt the partition without that usb stick.
> In case you forget to load that usb stick having the encryption key,
> there is a general manner to unlock the machine by feeding it a long code.
> Looks great isn't it?
> So far the paper...
> But now the usual bug; the implementation that practical was allowed by one 
> those guys on the Perry-Sport mailing list.
> Of course we don't want to tire ourselves too much typing too long unlock 
> codes...
> That unlock code, stored at a different USB stick is 48 digits.
> By the way 48 digits is how many bits?
> Right, that's less than 48 * (log 10/log 2) = 160 bits.
> So the problem for our first year student has been brought back from 256 to 
> 160 bits already.
> Not that it is a hobby mine, but one day i rebooted the machine and had 
> forgotten to put in the USB encryption stick.
> By accident i mistyped the key. Windows then told me:
>   "you made a mistake somewhere in those 5 digits of the 48 digit key, 
> please retype them".
> Doh.
> So my guess is that soon i do not need to worry when by accident i lose that 
> USB stick...
> Vincent
> </EOF rant>
> On Jun 19, 2008, at 2:41 AM, Perry E. Metzger wrote:
>> Jim Lux <James.P.Lux at jpl.nasa.gov> writes:
>>> In general, fundamental research is not subject to export controls, so
>>> if you frame your problem in terms of abstract mathematical problems,
>>> you're not going to be treading on any toes.  However, start
>>> distributing it as "Jim Lux's superduper encryptor/password cracker,
>>> now with 1024 bit capability!" and it's moved from fundamental
>>> research to a product.
>> Under current rules, provided it is open source or generally available
>> to any buyer, you can distribute and export cryptographic code quite
>> freely. There are some minimal reporting requirements, but they're
>> barely worth mentioning.
>> That's the reason you can freely distribute things like Kerberos,
>> OpenSSL, pgp/gpg, etc.
>> Perry
>> -- 
>> Perry E. Metzger		perry at piermont.com
> _______________________________________________
> Beowulf mailing list, Beowulf at beowulf.org
> To change your subscription (digest mode or unsubscribe) visit 
> http://www.beowulf.org/mailman/listinfo/beowulf

Robert G. Brown                            Phone(cell): 1-919-280-8443
Duke University Physics Dept, Box 90305
Durham, N.C. 27708-0305
Web: http://www.phy.duke.edu/~rgb
Book of Lilith Website: http://www.phy.duke.edu/~rgb/Lilith/Lilith.php
Lulu Bookstore: http://stores.lulu.com/store.php?fAcctID=877977

More information about the Beowulf mailing list