Attacking Diffie-Hellman

Part II of the series Diffie-Hellman key exchange.
August 22, 2015

Part I of this series established the conceptual framework for Diffie-Hellman, so now we can turn to more pragmatic matters: attacks on Diffie-Hellman. Naively, the only way to calculate x where a^x\pmod{n} = m is to calculate a^1\pmod{n}\\a^2\pmod{n}\\a^3\pmod{n}\\\ldots\\a^x\pmod{n} until we hit a match. The worst case of this algorithm is \mathcal{O}(n) , which means that the time required to brute-force a shared key grows exponentially with the bitlength of the key.

However, there’s a number of algorithms1 that allow us to compute the discrete log of any finite cyclic group in about \mathcal{O}(\sqrt{n}) time, and modular exponentiation, being a finite cyclic group, is vulnerable to these attacks. Fortunately, this is a square-root of an exponential, so an attacker using these algorithms against a 128-bit key would be about as fast as an attacker using the naive brute-force algorithm against a 64-bit key, which doesn’t seem to be too bad of a tradeoff.


Macbook-style Suspend on Linux

July 2, 2015

Macbook envy

Macbooks enter suspend really gracefully, which is something I never really missed on my Arch box until I actually started using suspend1. Here’s how I got my computer to:

  • Dim the display twenty seconds before suspend

  • Cancel dimming and suspend if any mouse or keyboard input was detected during that twenty seconds

  • Not dim/suspend if there was any sound playing

How even do you suspend?

A quick trip to the Arch wiki tells me that suspend works out of the box with a systemctl suspend. That was great, but I didn’t want to manually put my computer to sleep every time I thought I wouldn’t be using it for a little while.

Attempt 1: xautolock

xautolock checks if there isn’t any X Window activity within a certain interval, then calls an arbitrary command. I tried it out:

xautolock -time 2 -corners x-xx -locker "systemctl suspend"

The -corners x-xx parameter meant that moving the mouse into the top right-hand corner would disable the autosuspend, which I thought would be pretty useful for watching videos.

This worked fine, except that I’d be looking at something for a little while, and if I didn’t touch my mouse or keyboard, my computer would suddenly suspend itself. Fortunately, xautolock has a -notify flag, which lets you run a command some interval before the actual suspend.

Some people had the -notify set up for a notify-send call, but I didn’t want to start using an entire notification system just for getting notified of an impending standby, and the notification systems I did try didn’t play very nicely with i3.

I decided to keep looking.


Dog Fur Donuts

Part I of the series Diffie-Hellman key exchange.
May 11, 2015

Perfectly Secure

“I have it!”, Alice yells out to anyone who can hear her. Donuts are stacked precariously around her, gleaming in the fluorescents of her parents’ kitchen. She feels like a giant in a confectionery skyline. Which is what she wants, really. Her donut stand is about to pay for a new TV for the living room, entitling her to watch an entire season of House of Cards. Dad had promised.

Figure 1 · Alice, eight year-old donut prodigy.

Figure 1 · Alice, eight year-old donut prodigy.

Alice holds her wooden spoon aloft, victorious. She’s just created the most delicious donut her neighborhood will ever taste. But first, she’s got to check with her best friend, Bob, who really knows donuts…

The spoon lowers as she remembers Bob’s sister, Eve, a teenage brat who steals all of Alice’s recipes and posts them on a recipe site, where they are Five Starred and accrue glowing comments1. Alice has tried to use codewords for ingredients, or writing in really tiny letters, but somehow the recipes keep popping up online, just a few hours after Alice sends the recipe to Bob.

No way it’s happening to this recipe, Alice thinks. She needs a secure way to send her recipe to Bob, so that even if Eve intercepts everything Alice sends, Eve won’t be able to make any sense of it.

Alice brings up Google and slowly types her search query: perfect encryption.


Organs for sale

March 12, 2015

I was reading an essay by Leon Kass called “Organs for sale?”1, which argued against organ transplantation markets, and it kind of rubbed me the wrong way, so I decided to collect my thoughts here. It’s not so much that I disagree with his position- organ markets come with a whole thicket of tricky moral issues, and I’m in broad agreement with many of his conclusions. It’s the way he justified his conclusions that left me rather nonplussed.


Kass begins by recounting his precognitive repugnance toward organ transplantation, claiming he was “repelled by the prospect” of even reviewing an article on the matter. He notes the difficulties in holding this view, admitting that “regardless of all my arguments to the contrary, I would probably make every effort and spare no expense to obtain a suitable life-saving kidney for my own child.” Despite these tensions, however, Kass feels this attitude is tenable precisely because it acknowledges the ethical dilemmas he believes to be irreducible, instead of explaining them away in a neat utilitarian calculus.



May 4, 2014


I feel compelled to talk about Peter Singer’s moral philosophy for a bit, because I think he makes a distinction that is often elided in many discussions. Singer’s philosophy is only obliquely/ analogically related to the thrust of this post, so don’t come away thinking that I want to inculcate you with Singer’s philosophy or anything1.

Singer is an act utilitarian, which roughly means he thinks morality is defined by actions and their effect on the sum total of good2, and more specifically, a hedonistic act utilitarian, which means he thinks the good may be defined as the net suffering or happiness of sentient beings. Importantly, this forms the only basis for judging moral values, so actions are moral only and exactly to the extent that they affect suffering or happiness. That’s basically all that’s in the Singer Starter Kit- the rest is spectacularly extrapolated from there.

That unflinching internal self-consistency is what’s so seductive about Peter Singer’s work. Just like you aren’t forced to accept that Euclidean geometry maps directly onto physical reality3 to nonetheless go all mushy when we trudge along the hypotenuse from axiomatic base camp to soaring propositional summit, you don’t have to be a hedonistic utilitarian to be positively enchanted when Singer sets things up just right and these elegant little moral precepts come pirouetting out, and you gingerly pick them up and sort of heft them in your palms and just watch them go about their day.


Previous Next