Wednesday, April 21, 2010

Map of a Tweet

Raffi Krikorian, a developer on Twitter's API/Platform team, has produced a map of the information required to represent the status of a Tweet in JSON format, and its perhaps more complex than you thought (way more than 140 characters). Great graphic, and already 30,000 views on Scribd.


Reblog this post [with Zemanta]

VeriSign checking 2 billion certificates a day now

VeriSign announced last week that 2 billion certificate verification requests were made to, and handled by, its trust infrastructure. Version 3 of  X509 certificates contain an extension for listing a URL to a Certificate Revocation List (CRL) distribution point, where the status of a given certificate can be verified. So for example if you make an SSL connection and wish to check that the server certificate has not been revoked, then your browser can look for a CRL distribution point in the certificate and hand it off to an Online Certificate Status Protocol (OCSP) handler for checking.

Here is a quick overview of the use for OCSP in a typical online transaction scenario (from TORSEC), and you can think of VeriSign acting as the CA and provider of its own OCSP responder


In the early days of PKI there was a chicken-and-egg problem in that certificate providers did not make use of the CRL extension because browsers did not make the checks (there was no OCSP), because the certificates did not have a CRL extension, and so on.  But OCSP checks seems alive and well today, made each time a user initiates a smartcard logon, VPN access or Web authentication. In fact, VeriSign has seen OCSP traffic double in less than a year.

Reblog this post [with Zemanta]

Tuesday, April 13, 2010

AES-128 versus AES-256

Last November I posted about an email response by John Callas, CEO of PGP, trying to dispel the perception that a government agency might have the computing power to break 128-bit keys. People seemed concern that while breaking 128-bit keys is beyond the resources of most people or groups, governments agencies still had a good shot. He thought this extremely paranoid, using the example of a computing cluster that enveloped the entire earth to a height of one metre high would still require 1,000 years on average to recover a 128-bit key.

I just put up on Scribd a 2008 whitepaper from Seagate that discusses their reasoning for choosing AES-128 over AES-256 for hard disk encryption. The whitepaper states that
  • NIST has concluded and recommended that all three key-lengths (128-bit, 192-bit and 256-bit) of AES provide adequate encryption until beyond calendar year 2031.
  • NIST’s recommendation above includes the threat model not only of predicting the key, but also of cracking the encryption algorithm. The difference between cracking AES-128 algorithm and AES-256 algorithm is considered minimal. Whatever breakthrough might crack 128-bit will probably also crack 256-bit.
Further, Seagate wanted to maximize the success of its solution by considering the additional business-side concerns:
  • Must promote compliance with laws controlling export from the U.S. and import to other nations
  • Must be cost-optimized
  • Must be able to meet the needs of ALL target markets
AES-128 is sufficient or exceeds all the above criteria.
They also went on to discuss the computational task of recovering 128-bit keys, where assuming
  • Every person on the planet owns 10 computers
  • There are 7 billion people on the planet.
  • Each of these computers can test 1 billion key combinations per second.
  • On average, you can crack the key after testing
    50 percent of the possibilities.
it follows that the earth’s population can crack one encryption key in 77,000,000,00,000,000,000,000,000 years! The graphic form of the argument looks like


Nonetheless AES-256 is being widely deployed since it conveniently lies at the intersection of good marketing and pragmatic security. In upgrading from AES-128 to AES-256 vendors can legitimately claim that their products use maximum strength cryptography, and key lengths can be doubled (thus squaring the effort for brute force attacks) for a modest 40% performance hit.

Monday, April 12, 2010

“Asynchronous” Quantum Cryptography

The MIT Technology Review has reported a breakthrough in quantum cryptography from Anthony Laing of the University of Bristol, and several colleagues. While quantum cryptography promises to furnish unbreakable key exchange protocols for example, there are many practical problems to be solved before such systems can be considered industrial grade. The main drawback is that quantum cryptography

can only be used over point-to-point connections and not through networks where data has to be routed. That's because the routing process destroys the quantum properties of the photons used to secure messages.

The relevant properties of the photons are maintaining perfect alignment so that polarisation measurements at the receiver can be done accurately. But unfortunately network or satellite routing is not very alignment-friendly.

Laing and his colleagues have devised a way to circumvent the alignment problem by encoding an additional dimension in the qubits that is independent of space. In physics jargon the qubits are “reference frame independent”, making their encoded information far more robust to transmission. This reminded me of asynchronous data communication where timing information is sent as part of the data so that the sender and receiver do not need to maintain common clocking information.

Full paper here (4 pages).

Reblog this post [with Zemanta]

A functioning Turing Machine

Mike Davey from Wisconsin, who describes himself as someone who “always liked to make things”, has created a fully functioning Turing machine. Many computer scientists such as myself went through at least one class where we had to learn about the theoretical intricacies of Turing’s manifestation of a computable (mathematical) function – tape, symbols, reading, writing, erasing, alphabets, halting states and so on. Well that all would have been a lot more concrete and interesting with Mr. Davey’s device at hand, shown below


Please visit his site, the aptly named, to see a video of the machine in action. The device is driven by a microprocessor but the “computations” - moving the tape and changing its contents under the “head” - are quite faithful to Turing’s description. The tape is not infinite but rather 1000 foot roll of white 35mm film, where binary characters can be read, written and erased. Mr. Davey says he is not deeply attached to his creation, and may be willing to part with it in a year or so.

Wednesday, April 7, 2010

GPS and Road Privacy

The Las Vegas Sun has reported that the GPS tracking of drivers is being considered as a technology to support expected shortfalls in fuel taxes. The Nevada Department of Transportation (NDOT)  revealed at a meeting this week a study which estimates that reduced fuel taxation revenues due to the use of hybrid and gas-free cars could be as high as $6 billion by 2016.
Nevada is considering several schemes to support a payment model based on "vehicle miles travelled", including voluntary reporting (the honour system) all the way up to on-board GPS-based devices for wireless tracking of miles driven. While this may seem a wonderful opportunity for technologists to rollout a sophisticated system, privacy concerns were raised immediately.
Scott Rawlins, NDOT deputy director, said privacy is a central issue in the debate. "Some say we don't want Big Brother following us around," Rawlins said. "How do we protect the privacy of those vehicle owners and not have that sense out there?” No simple (or complex) answers to the privacy issue as yet.
In June last year I made a long post on the risk of degradation to the GPS service, based on an assessment of the GPS program by the Government Accountability Office (GAO), the audit and investigative arm of the US Congress. The GPS privacy debate may yet be moot.
Reblog this post [with Zemanta]

Tuesday, April 6, 2010

Monthly Round-Up, March 2010

March was a strong month for visitors (over 2,300) and page views (over 4,400). I was hoping for my first “222” month where I could claim at least 2,000 visitors, viewing on average 2 pages for 2 minutes. Everything was on track until I made a short post on a password joke and well, hundreds of unexpected people visited for a quick read, giving more visitors but driving page views and visit times down. Oh well.

There were a few posts on RSA. The first on a service that will recover 512-bit keys in 2 weeks for $5,000, and the next two on the RSA power attack – beginning with a summary of the technical details from the original research paper, followed by clarifications on the significance of the attack, mainly from other bloggers.

There were also several other technical topics I posted on which have been backing up for a while now. I made a few remarks on the completion of the rainbow tables for GSM encryption in The Last Days of A5/1, and some background on the encrypted search breakthrough from mid 2009 in In Search of Encrypted Search (this post is on the first page returned by Google for “encrypted search” so I might have to make it a little more comprehensive).

I also posted on the The Re-Keying Conundrum in light of modern encryption algorithms, prompted by the remarks of Eric Rescorla, who is fresh from completing a proposal for circumventing the well-publicised TLS Renegotiation Attack. There was also an improvement to LanMAN hash searching from the inventor of rainbow tables, yielding a 300 billion per second search rate for these (weak) password hashes.

In the odds and ends department, I finally found out how likely a 25 sigma event actually is (rarer than winning the UK Lottery 22 consecutive times), reported that The ISACA Risk IT Framework is rising on Scribd (about 4,500 reads now), remarked on Passwords for USB Keypads, and mentioned a few more giveaways for the Microsoft SDL. Also MoMAacquired” the @ symbol, and I looked back at the posts I was making a year ago.

Finally in the humour department there was that password post and some beautiful observations on a  Bruce Schneier Post Template.