Quantum computing, privacy, and why it’s just business as usual

•October 31, 2012 • 1 Comment

Every so often I’ll see someone trying scare people into believing that quantum computing will bring an end to privacy. The truth is quantum computing is simply the natural advancement of computing technology and cryptographers will take this into account when designing new cryptographic schemata. However, the true issue at hand is the use of protocols that are inflexible to where it is non-trivial to use updated cryptographic schemata. I will explain why here, and why it’s not the end of the world.

On Symmetric Algorithms

I have seen cases when someone would claim that quantum computing will be able to break a 256 bit AES key in an instant. This is simply not true. The advantage that quantum computing brings is that computers will be able to run more algorithms, some that will have run times much faster in relative the size of the input data versus algorithms that can be run on conventional computers. This means that individual mathematical operations will be faster on a quantum computer. This does not make a huge impact on symmetric cryptographic algorithms like AES.

Symmetric algorithms derive their strength from repetition. Operations in a symmetric algorithm have very little relation to at least one of either the key, the plain-text, or the cipher-text. This means that methods to break strong symmetric algorithms are often described as requiring more time than the age of the Universe and more memory than the capacity of all hard drives on earth, usually by several orders of magnitude.

Accelerating individual operations does not change this. Some aspects of quantum computing can solve the issue of the amount of memory required, but quantum computers are not able to handle algorithms that have long run times. Quantum computers are probabilistic machines. Information in a quantum computer degrades over time, so the longer the run time, the weaker the relation between input and output.

On Asymmetric Algorithms

The quantum algorithm that I have seen most commonly referenced in media is Shor’s Algorithm. Shor’s Algorithm is a fast method of factoring large numbers. This is significant in that it does produce a method of attacking the commonly used RSA encryption much faster than is possible with conventional computation. Right now it is very common for RSA to be used with 1024 bit keys. Those 1024 bit keys are really just one big number that happens to be the product of two prime numbers. Once those prime numbers are found the key is broken.

Shor’s Algorithm requires a quantum computer with two times more qubits than the number of bits in the number to be factored. At this time, a company called D-Wave claims to be in production of a 512 qubit computer. Other claims indicate that the NSA has one and will use it to predict the future. Marketing nonsense and insanity aside, we can assume the computer is real. A 512 qubit computer does not break modern cryptography, but it does break cryptography that should have stopped being used 5 to 10 years ago. More importantly is when a 2048 qubit computer is made available. Something of that calabure will be able to break the majority of cryptography used on the internet today and, as things are progressing, this will likely happen in 2014 or 2015.

I know it sounds grim, but this has happened before.

Up until 1996 there were strict laws in place in the U.S.A. that restricted the level of security that any cryptographic algorithm exported from the U.S. may have. In theory this was to prevent enemies of the U.S. from acquiring cryptography that is too difficult for U.S. intelligence agencies to decipher. In practice it only prevented U.S. citizens from acquiring strong cryptography.

The most commonly used encryption protocol is SSL. SSL describes how two computers that want to communicate with each other should decide upon mutually compatible methods for forming a shared secret key, for authentication, for encryption, and how to transmit encrypted message across the internet. The security of SSL is very implementation dependent. SSL includes code for strong encryption that was written outside of the U.S.A., and because of this it is not subject to U.S. export law when used outside the U.S. However, U.S. law ironically prevented a full spec version of SSL from being distributed to U.S. citizens. A separate version had to be distributed within the U.S. with a key length limit of 40 bits. To put that into perspective the complexity of breaking an ideal cipher should increase by a factor of two for every additional key bit. DES a symmetric encryption algorithm used in those days has a key size of 56 bits. By 1992 DES was already proven broken, and by 1997 a message encrypted using DES had been publicly deciphered.

Those were bad times for cryptography, but the world still turns.

Why it’s all irrelevant

If you’re like most people, and most people are, then your greatest need for encryption will be whenever you log into a web site or make online orders. Someone with a 2048 qubit quantum computer would definitely be a concern to you, but that’s not really you only concern. The type of online activities will require the use of SSL, and even a proper, strong, modern version of SSL still has the weakness of requiring a certificate authority to affirm that the computer that your computer talks to is owned by who it says it’s owned by. What this means is that ever since the early days of the use of SSL anyone sufficiently good enough at lying could get a certificate from a certificate authority in the name of your bank. Then, if they can intercept internet traffic between you and your bank, they would be able to impersonate your bank in a very convincing manner and read your log-in information once you send it.

The only way that quantum computers changes this is that, rather than asking one of many CAs for a new certificate for a cost of about $100, someone could buy a quantum computer for millions of dollars to break and use existing certificates. Also, keep in mind that some CAs have had a history of not doing enough to verify the identity of the people requesting certificates.

What we can do today

As a temporary patch, existing authentication and encryption methods can still be used a couple more years by extending the keys used. A 16Kibit RSA key can be generated in just a few minutes and should be strong enough to be unbreakable until 2018 to 2020. However, there is an issue here where some implementations of SSL are not able to handle very large keys.

To address SSL’s limitation in its authentication there are a few projects to extend it. Such extensions will still have there limitations, so I can’t recommend one, but it’s not hard to improve upon a system where the weakest link in a chain will be attacked.

The attack against SSL I described is called a “man in the middle(mitm)” attack. To learn more about this and others and ways to protect yourself I recommend educational material like Hak5.

For private communications I recommend not deferring to a third party for encryption and authentication. Any certificate authority will be subject to social engineering, and may not use keys of sufficient strength. For private communications I recommend applications like GNU Privacy Guard that let you handle the authentication directly and update your keys as needed.

What is being done to address quantum computing directly

Quantum computing does not magically solve all math problems. Smart mathematicians are working on a few candidates to replace the RSA/DSA/ECC algorithms used today. One of the candidates that is considered to be the most promising is NTRU. NTRU is a form of lattice-based cryptography. Even in light of the known abilities of a quantum computer, lattice-based problems are described as being moderately hard to very hard. That’s “very hard” as in it can’t be solved before our Sun blows up unless you find an easier way to solve it.

Laws restricting cryptography in western countries are much fairer now, and with AES we have symmetric encryption that will easily last the next few decades and we already know enough about the weaknesses of AES to begin replacing it. Soon, once we have a method of key exchange and authentication that can stand against quantum computing, thee of the four fundamentals of cryptography will be strong.

Spirit From Above: The City

•October 18, 2011 • Leave a Comment

The following is a work of fiction. It does not describe actual event occurring in a distant part of the galaxy. Anyone who states otherwise is a crazy conspiracy theorist and should be ignored.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.

This is an ongoing story. I am writing this in my spare time. To see more sooner make a donation.

Copyright 2011 Steven Hystad

In a star system in a distance part of the Milky Way Galaxy there exists a nation of people who know no limits. The people of this nation have access the the most advanced technology in the galaxy. Physical enhancements give them great strength and endurance. Mental enhancements give them clarity of thought and telepathic ability. The second planet in this system is covered by one great city known as Adamant City. The buildings are tall, and food is automatically produced in mass, allowing for a population of greater than one trillion. There is no government to produce laws. There is no one to enforce laws. The only prevalent force is the desire to be entertained.

In the pursuit of entertainment the people of Adamant City have many tools. From videos and video games, to the most artistic form of food preparation, to the very fabric of pavement made to react to the desires of the people present, everything is made to entertain. However, the pursuit of entertainment is as endless as The City itself. There exists a class of people known as “channel operators” in Adamant City who have taken up the task of expanding the vast media library of The City. There also exists a class of people known as “protagonists” who play the role of the star in the media produced by the operators.

I am one such channel operator. My name is Voice Of Illumination. I will bring you the story of one man who has agreed to be my protagonist. His name is Spirit. Spirit and his team recently won the Galactic Tactical Competition, a tournament of the best of the best gamers in the system and features many excellent gamers from around the galaxy.

I personally spoke to Spirit telepathically after his victory, “Forgive me for interrupting your moment of glory, but I have a new challenge for you if you’ll accept. I am the channel operator Voice of Illumination. I am in need of a protagonist for a new series to be shown on my channel. I should like that to be you. Clear any obligations you may have and head to Space Port Lambda.”

Spirit and his team stood amid the closing ceremony, on a stage, to be seen by the other competitors and many observers that came to see the tournament in person. An interviewer was speaking with Spirit’s teammates. Spirit’s response to me was, “I think I already know what you’re planning. This isn’t the first time a channel operator has asked a gamer to become a protagonist and head to a space port. But I will not tolerate any boredom. If I go I’ll be playing by my own rules.”

“That’s fine. I just want to send you to places across the galaxy where there is great turmoil, follow you with a sentinel camera, and watch how you resolve the situation.”

“Are you sure? Sounds boring to watch to me. It’s always more exciting to be on the field than to watch, but if you think you have something for me to do that may be worth watching then I’m in.”

The interviewer turned to Spirit and spoke to be heard by the audience, “That was quite a decisive victory, can you tell us what the key to this victory was?”

Spirit faced the audience. “Know your enemy. When working as a team, know your team members, and apply their talents in the best way possible. Ultimately the key to victory is desire. Even when you can ask someone for help, you need to be willing to put forth some effort towards your goal. If the only effort you put forth is to force someone else to give you what you want, then you will only annoy them and either get nothing from them or get something you didn’t want. Also, remember that building a team means building team members. When someone makes a mistake, don’t scold or taunt them, just recommend a better course of action for them to take in the future.”

The interviewer again spoke to Spirit, “Can we expect to see you at the next tournament?”

“It seems I will be leaving The City indefinitely. So I wont be making any reservations for the next tournament.”

Upon hearing this, the crowd roared. After the crowd calmed the interviewer turned to Spirit with an expression of astonishment. “Can you offer any explanation for that?”

“I’ll be working with Voice Of Illumination for a while. If you want to see more of my great victories then subscribe to his channel.”

As the closing ceremony ends, both participants and observers make their way out of the stadium and onto the platform of the bus way outside. Numerous mass transit vehicles suspended from overhead monorails approach the platform, pickup waiting passengers, and disappear into the distance to deliver each passenger to their destinations. Above can be seen another platform where people may gather to perform recreational activities much more casually than what was previously seen in the stadium.

Spirit walks toward the edge of the platform, and a car arrives. This car has ten seats but twenty people follow Spirit on. Each passenger has their own questions for Spirit, and he does his best to answer them all. The car makes three stops and at each stop a group of passengers disembarks, making a more peaceful environment each time.

After the third stop, Spirit is left alone for the long travel to Space Port Lambda. Spirit takes a seat and looks out the windows to admire The City that he will be leaving behind. To the left and right are the great monolithic walls of the buildings in The City. All are constructed of synthetic black diamond, and many are polished to produce a dark mirrored finish. Above and below, innumerable platforms extend from the buildings.

The car now moves to an express lane and increases speed. To the left and right are several other high speed monorails. Cars are seen going back and forth, but resemble more a blur of light than a car. Below is seen a vast greenhouse containing thermo-synthetic plants. The plants are producing fruit from the great amount of heat generated in The City.

The monorail rises above the buildings. The sun lit sky shone brightly, illuminating the tops of the buildings. Everywhere that can be seen is a view of a greenhouse. Producing food and oxygen for more than one trillion people is an immense task, and one that is taken seriously.

Ahead, rising over the horizon is Space Port Lambda, a massive structure towering over the other buildings. The base of this structure is wide, and, above, are seven pilers in hexagonal formation rising up into the distant sky with crossbars interconnecting them. The car slows as it approaches the base of the space port. Once inside the space port, thousands of docked spacecraft can be seen above.

The car takes a branch rail and approaches a platform. The car stops, and Spirit walks out.

Song of the Crow

•April 7, 2011 • Leave a Comment

When it comes to writing, poetry is not my strong point, but I felt the need to post the following piece. As a forewarning I did not make any serious attempt at format as the only poetry I have written before has been haiku. As an additional warning the word choice in this piece is euphemistic, for a reason I will explain after the piece.

Title: Song of the Crow

Here I am, the crow.
My wings are wide and shimmer in the light of the Moon.
No object has ever obstructed my path;
just a flap of my wings and everything is distant below me.
I spot a herd of sheep,
and swoop down to take a look.
The sheep say “baa,”
but I don’t understand their words.
I flap my wings as if to perform a dance,
and the sheep flee from me, “baaing” as they go.
Latter I settle down near a bonfire,
eating a fresh piece of fruit.
My hunger is eternal,
every byte I take makes me more hungry.
As my own hunger devours me,
I search for more food.
I smell the sent of pastries nearby.
I approach and see a pretty girl,
in a crimson dress, with gold hair.
She is taking delight of the taste of chocolate.
“Mr. Crow, wont you have some chocolate with me?”
My hunger forbids me to deny her,
and I eat as though I have never done so.
The sustenance is too late for me,
I collapse, and fall to the ground.
I awaken to find myself in a silver cage,
It’s bars shine like the Moon.
I flap my wings,
but one no longer shimmers.
A cage like this is not good enough to hold me,
and I escape, even if with only one wing.
My escape from the cage is not unnoticed.
“Play a game of tag with me”
That silly girl smiles at me,
her grin outshines the Moon.
I fly out the window.
She tags me on the wing,
the shimmering light of the Moon shatters,
and I fall to the ground once more.
I hop around the ground,
we play her game of tag.
As we run around I glimpse the shimmer of the moon,
I return this simmer to my wing,
but another tag from the girl shatters it,
it’s pieces dance and fall around us like snow.
The insignificant now appears monolithic.
As I grow weary I fear the next tag may be the end of the game.
She sees my exhaustion,
and returns me to the silver cage.
Her laughter indicates her enjoyment.
“I only get to talk to dolls here, Mr. Crow,”
“So can you teach me a song before you sleep?”
I know only one song,
I sing the song of the crow.

Note that the last four words are also the title. This was not intentional, but accidental. I wrote the title first before writing the body of the poem. It just worked out that way.

The reason why I wrote this poem was because I was listening to the song Sweets Time Midnight for far too long. I wanted to write something using the same type of word choice as in that song. Now to clarify the meaning of the above text I will translate some of the words used. The crow character is meant to represent a young vampire struggling with an unusually strong hunger for blood. This character may be viewed as wearing black clothing, and wielding two bladed weapons. This character is a particularly talented twinblader and has an invincibility complex. This invincibility complex is replaced with an unfamiliar anxiety when “Mr. Crow’s” weapons are lost. The shimmering Moon light on the crow’s wings is meant to represent the twinblader’s weapons. The sheep are humans. The fruit and sweets are human flesh. The pretty girl is based on Flandre Scarlet. The silver cage is a room with mounds of human skeletons. The game of tag is a fight for freedom. The word “dolls” was used in Sweets Time Midnight to represent human corpses. Songs are screams.

Another parallel between Sweets Time Midnight and Song of the Crow is that both speak of a bird. Sweets Time Midnight features a bluebird. The bluebird is presumably a human and meets its end by the hand of the Scarlet Devil. Our crow here is vampire and quite talented at his choice of weapon, but is still quite young and doomed to face the same fate as the bluebird.

Now with the meaning of the words of the poem explained you should now reread the poem. The poem should now give much different visual information, telling a much darker tail. If so then this experiment has been a success. If not, feel free to tell me it sucks. You would not hurt my feelings. Even with my own artistic ability for word choice I wasn’t quite able to tell the story the way I wanted with all the detail I wanted without giving too much detail about what was actually happening.

Despite not being 100% happy with how the poem turned out, this experiment does lend itself as a tool to be used in future writing. I’m not sure if I will be writing poetry like this in the future, but I may use the same kind of euphemistic speaking for the dialog for some mad man in any narrative I might write in the future.

Army of Hippopotamuses of Doom

•August 24, 2010 • Leave a Comment

After the recent launch of our new line lazer sidearms, the feed back we received was mixed. The open letter we received from The League of Alien Invaders was quite positive, saying that our product was quite beneficial to their conquests. However, we received a somewhat less glowing review from the Army of Hippopotamuses of Doom. They informed us that our sidearms were difficult for them handle. Specifically they said that with their large fingers they could not fire the weapon.

In response to this our R&D department has developed a specialized weapon for use by hippos. The hippo mounted lazer turret. This new weapon is of a much higher caliber than the lazer sidearms. It is designed to be mounted on the backs of the hippo soldiers and to be operated a lemur. This choice was made because it is known that the Army of Hippopotamuses of Doom have a division for ninja lemurs. While it was specifically designed to be operated by a lemur, it could also be operated by many other small furry animals but little testing has been performed outside of being operated by a lemur.

A private demonstration has already been held with the Army of Hippopotamuses of Doom, and the initial feedback is positive. We are now negotiating the contract with the Army of Hippopotamuses of Doom.

Multithreading In Powershell Version 2.0

•December 5, 2009 • Leave a Comment
Starting with version 2.0, Windows Powershell has a set of cmdlets that allow scriptblocks to be run asynchronously. The interface it gives is in some ways similar to what I did in Library-AsyncRunspace.ps1, but different in many other ways. This is likely due to different interpretations of complexity theory. One notable difference is that my script library allowed for runspaces to be initialized and used with more than one scriptblock, while the jobs in Powershell v2.0 cmdlets seem to use one time use runspaces.

The examples for background jobs in Powershell v2.0 are pretty simple. To start a job use start-job.

$job = start-job { ps }

It returns an object that identifies the job. Objects can be piped into the start-job cmdlet and that input will be made available to the job. We then can get the results using the receive-job cmdlet.

Receive-Job $job

Receive-Job will return all results up to that point in time and return. To get all results we must first wait for the scriptblock to finish processing using the wait-job cmdlet.

Wait-Job $job

You can also wait on multiple jobs.

Wait-Job $job1, $job2

Job identifiers are saved and can be retrieved using the get-job cmdlet.

get-job

The result is a list of all parent job identifiers. (Read the about pages for info about parent and child jobs.) Specific jobs can be recalled by their id number or name.

get-job 1, 3, 5
get-job MyFirstJob, MySecondJob

Jobs can be listed by state.

get-job -State Running

You can cancel a job by using the stop-job cmdlet

stop-job $job

The Remove-Job cmdlet will force powershell to forget about past jobs. The line here removes all jobs that have completed.

Remove-Job -State Completed

Or to remove only completed jobs where all output data has been read.

Get-Job -State Completed | where {$_.HasMoreData -eq $false} | Remove-Job

See about_jobs for more info.

About The Powershell Host Object

•October 26, 2009 • Leave a Comment

I got the following query in one of my Google hits today: "pipeline.Invoke() "Read-Host" Cannot invoke this function because the current host does not implement it."

I believe that this query was in reference to the lack of host functionality in the default settings for a runspace in Windows Powershell. I don’t recall ever actually taking much about this, yet I am known for having abstracted the runspace API for use as a multi threading interface in Powershell. Now is a good time to talk some about this.

A runspace in Powershell is a big blob of information that pertains to a particular shell within Powershell. The runspace has several components within it, such as the cmdlets, aliases, functions, providers, etc. The host component specificly is ment to be used as an abstract interface to the console. The default host object used by a runspace doesn’t have much functionality, so you may encounter error messages like the one above when you are using a generic host object.

It is possible to tell Powershell what host object should be used when the runspace is initialized. I do know that version 1.0 of powershell.exe will use a host that writes to the console used by the powershell.exe process. Since most other instances of Powershell don’t have a console the host object will often be the default host object, that doesn’t provide any functionality on its own, or a very simple host object, using only implementing a few methods in the PSHostUserInterface class.

From the query above it looks like this googler was trying to use Read-Host within an asynchronous runspace. The easy solution to this is to just not do so. It’s easier, in most cases, to simply pass the needed information into the asynchronous runspace from the parent runspace. However, there are still some cases where you must use Read-Host from an asynchronous runspace. In that case you’ll have to code and compile your own host class, and use that when initializing the runspace.

Powershell, String Encryption, and GPG

•October 23, 2009 • 2 Comments
I finally added support for GnuPG to Library-StringCrypto. The previous functionality to encrypt strings in process is still present and continues to work as expected. Now a couple more parameters have been added to support symmetric and asymmetric encryption using GnuPG.
The new parameters are ‘gnupg’, to enable use of gpg.exe, and ‘recipient’, to identify the person the encrypted message is for. When using GnuPG passwords/passphrases may be supplied in ‘password’ parameter or via the console to the gpg.exe process.

To use symmetric encryption, with GnuPG just add the gnupg switch parameter.

Write-EncryptedString message secret -gnupg

You can also omit the password from the command line and enter it interactivly.

Write-EncryptedString message -gnupg

To use asymmetric encryption, omit the password and use the recipient parameter.

Write-EncryptedString message -gnupg -recipient ‘John Doe’

Write-EncryptedString returns the ASCII armored version of the ciphertext. Read-EncryptedString will be able to detect the ASCII armor and automatically process it using gpg.exe. Decryption should just work as expected. The password parameter can be used for both symmetric and asymmetric encrypted messages. Also the passphrase may be interactively entered via the console to gpg.exe.

Usage notes: The command ‘gpg’ is expected to resolve to gpg.exe, so you may need to add a path entry or alias gpg to wherever your copy of gpg.exe is.
When the password is given via the password parameter, it is passed to gpg.exe as the first line of its standard input. This means the password will not show up in its command line. This also means that passphrases are limited to one line. No check is performed to ensure the password is not longer than one line. If the passphrase is longer than one line then only the first line will be used as key material, the rest will appear at the start of the decrypted message.

Some cryptanalytic stuff: Using GnuPG via this script should be no less secure than using GnuPG by any other method in Powershell. However, because this involves communication with another process, using GnuPG does have a larger attack surface for side channel attacks than simply performing the encryption using the CLR. i.e. Either your installation of the .NET Framework or your installation gpg.exe may be compromised, but gpg.exe alone being compromised does not effect the .NET Framework.

Download Library-StringCrypto.ps1 here.

 
Follow

Get every new post delivered to your Inbox.