Indistinguishability Obfuscation, or how I learned to stop worrying and love DRM

There’s a lot of hype running around about this:

Lots of excitable talk of “perfect security” and other stuff. One of the possible applications is supposedly quantum-resistant public-key crypto. But if you read into it, it’s actually a way of making code resistant to decompilation. So instead of creating a secret number that’s processed by a well-known algorithm, you create a secret algorithm that you can ask other people to run without fear of it being reverse engineered. So the “public-key” crypto is really shared-secret crypto with the secret sealed inside an obfuscated algorithm.

In other words, it’s bulletproof DRM. deCSS is even referenced (obliquely) in one of the articles as a use case.

Of course, this makes it in principle impossible to test code for malicious behaviour. You could insert a latent trojan into it and never be discovered, and it removes one of the most important security features of security software – auditability of the algorithm. For example, someone could write a rot13 algorithm and call it “encryption” and the only way to (dis)prove it would be to run a statistical analysis on the ciphertext.

So the question becomes – why would anyone allow IO programs to run on their systems? Virus scanners would be useless in principle. Performance, even in the most optimistic case, would be dreadful. And it doesn’t do anything for the end user that can’t be achieved by traditional crypto (barring the development of a quantum factoriser, and even that is not yet certain). No, the only people who gain are the ones who want to prevent the next deCSS.


Web of Trust vs Certificate Authorities – a hybrid approach

The only thing in engineering worse than a single point of failure is multiple single points of failure. A SPOF is a component that the entire system depends upon, and which can thus bring down the entire system single-handedly. MSPOFs are a collection of components any one of which can bring down the entire system single-handedly. The X509 certificate architecture is such a system.

The job of a public key encryption system is to transform the task of securely sharing secret encryption keys into one of reliably verifying publicly-available certificates. Any form of reliable verification must necessarily involve out of band confirmation of the expected data – if an attacker has compromised our communications channel then any confirmation could be faked just as easily as the original communication. Out of band confirmation requires an attacker to simultaneously compromise multiple independent communications channels – this is the rationale behind sending confirmation codes to mobile phones, for example.

The competing verification models

Public key encryption systems typically rely on one of two out of band methods – an Authority or a Web of Trust. An Authority is a person or organisation that is assumed to be both well-known and trustworthy. If a chain of signatures can be established from an Authority to the certificate in question, then the trustworthiness of that certificate is assumed. By contrast, a Web of Trust requires a chain of signatures to be established from each user to the certificate in question – each user acting as his own Authority.

The out of band confirmation of an Authority relies on the shrinkwrap software model – assuming that your software has been delivered via a trustworthy method, then any Authority certificates that were included with your software are by implication verified. A Web of Trust typically relies on personal knowledge – users are assumed to only have signed the certificates of those people they either know personally or have otherwise verified the identity of offline. In this case, “out of band” means “face to face”.

In addition, some PKI systems allow for multiple signature chains to be defined – this is typical in Web of Trust models where the intermediate certificates are usually controlled by ordinary users whose reliability may be questionable. Multiple chains mitigate this risk by providing extra confirmation pathways which collectively provide greater assurance than any single path.

In a Web of Trust model, each user is responsible for cultivating and maintaining his own outgoing signature chains. This means continually assessing the reliability of the downstream certificates, which even with the help of software tools requires a nontrivial amount of work. The reward for this effort is that the reliability of a well-maintained Web of Trust can be made arbitrarily high as more independent chains are established. An Authority model also requires a maintenance overhead, but Authorities are typically large organisations with well-paid staff, and the certificate chains are much shorter. Authorities also tend to use automated verification methods (such as emails) which can be used by an attacker to escalate from one form of compromise to another.

An Authority is thus more easily attacked than a well-maintained Web of Trust, but less easily attacked than a badly-maintained one, and more convenient for the end user.

Why X509 is broken, and how to fix it

X509 has several points of design weakness:

  1. CA distribution is done via shrinkwrap software – but since almost all software is distributed over the internet this is easily subverted.
  2. Only one certificate chain may be established for any certificate – multiple incoming signatures are not supported, so every chain has a single point of failure.
  3. All CAs have the authority to sign any certificate they choose – therefore if one CA certificate is compromised the attacker can impersonate any site on the internet. Thus every certificate verification has multiple single points of failure.

The first two flaws can be addressed by incorporating features from the Web of Trust model:

  1. Web of Trust for Authorities – browser vendors and CAs should agree to sign each other’s signing certificates using an established WoT, thus mitigating against the distribution of rogue certs. Signing certificates not verifiable via the WoT should be ignored by client software, and technical end users can verify the integrity of the entire CA set using established methods.
  2. Multiple signature chains – each public site on the internet should be expected to provide multiple independently signed copies of the same certificate. A site providing only one signature should be treated as insecure by client software.

The third flaw can be addressed by limiting the validity of individual CA certificates. Each signing certificate should contain a field restricting its signatures to a subset of the internet using a b-tree method. A given CA certificate would state that it may only be used to verify leaf certificates whose names, when hashed using SHA256, match a particular N least-significant-bits, where N increases as we travel down the signature chain. Client software should invalidate any signatures made outside the stated b-tree bucket, and deprecate any signing certificate whose bucket is larger than an agreed standard.

(It has been suggested that CAs be geographically restricted, however it is unclear how this could be enforced for non-geographic domains such as .com, and may conflict with a solution to problem 2.)

With these improvements, the Authority model would organically gain many of the strengths of the Web of Trust model, but without imposing a significant burden upon end users.

Text messages (iMessages) coming from email addresses when using iOS 7

If you have recently upgraded your iPhone (and you should, see, your iMessage settings may be messed up – this isn’t visible to you, but it is to your contacts. If someone is sending you text messages that appear to come from an email address rather than their phone number, then they have this problem – please tell them and send them here.

To check if you have the problem yourself:

  • Go to settings > Messages > Send and Receive
  • Under “You can be reached by iMessage at”, if your phone number is not ticked, you have this problem.

To fix (this worked for me):

  • Go to Settings > Messages
  • Turn off iMessage
  • Go to Settings > Cellular
  • Turn off Cellular Data
  • Reboot phone
  • Turn Cellular Data and iMessage back on
  • Go to Settings > Messages > Send and Receive
  • Under “Start new conversations from”, tick your phone number

If you want to fail back to SMS messaging when iMessage is unavailable, make sure to enable Settings > Messages > Send as SMS. This was disabled by default on my fresh iOS7, and can cause text messages to be mysteriously delayed.

For more detail on the problem, see

More JIRA shenanigans

As part of my ongoing project to put every management process possible onto JIRA, I have been working on a way to make our internal account codes smarter. Previously, I was using a custom field with predefined values for each account code – this worked well until I wanted to automate certain tests and actions based on account code metadata such as project start/end dates and approval matrices (this issue was also a significant problem). Two methods sprung to mind: either I could define a custom field that could contain structured data, or I could implement the account codes as Jira issues and use issue linking. In my solution I ended up doing a bit of both.

The advantage of using JIRA issues to store account codes is twofold: firstly I can define whatever custom fields I require to hold structured data (e.g. budget holder userids, timestamps) in a format that JIRA can easily understand; and secondly the financial administrators and I can manage this data through a familiar interface. The big disadvantage is that issue linking in JIRA is done through a separate interface from issue creation/editing, meaning a two-stage process for my users. The ideal solution would be a drop-down menu in the issue creation/editing screen, but this means using a custom field – and one I would probably have to write myself.

Being a typical sysadmin, I decided to hack something together with sticky tape and string. I found a likely-looking custom field in the form of the JIRA Database Values Plugin. Using this to tap directly into JIRA’s back-end database I can populate a drop-down menu using some horrendous left joins:

sql.query=select, cv1.stringvalue, cv2.stringvalue, cv3.stringvalue from (select id from jiraissue where project=10200 and issuetype=13) as i left join (select issue, stringvalue from customfieldvalue where customfield=10140) as cv1 on left join (select issue, stringvalue from customfieldvalue where customfield=10141) as cv2 on left join (select issue, stringvalue from customfieldvalue where customfield=10142) as cv3 on order by cv2.stringvalue, cv3.stringvalue;

rendering.viewpattern={1,(none)} {2} {3}

The joins are necessary because JIRA uses a relational back end which assumes a fixed number of columns in each table. It handles issues with custom-defined fields by storing the custom field values in a separate table with back-references to the appropriate row in the main table.

The JDVP plugin provides a pretty front end to a custom field that stores the primary key of a database row, which in this case is I can then recall the account code issue in a JSS script by passing the primary key to getIssueObject() – the example below is a post-function that I use in an approval workflow to ensure that nobody can approve his own request:

from com.atlassian.jira import ComponentManager

# Only perform functions on Travel Request issues
if(issue.getIssueTypeObject().getId()=="8") :
  cm = ComponentManager.getInstance()
  cfm = cm.getCustomFieldManager()
  im = cm.getIssueManager()

  accountCodeID = issue.getCustomFieldValue(cfm.getCustomFieldObject('customfield_10134'))
  acIssue = im.getIssueObject(int(accountCodeID))
  acBudgetHolder = acIssue.getCustomFieldValue(cfm.getCustomFieldObject('customfield_10070'))
  acEmergencyBudgetHolder = acIssue.getCustomFieldValue(cfm.getCustomFieldObject('customfield_10151'))

  # Set the budget holder to the account code's budget holder, unless that is the reporter.
  # The Java API for custom fields is crap. I'm using a trick here.
  # DO NOT USE issue.setCustomFieldValue() - it does NOT persist. This is a feature (!)

  if issue.getReporter() == acBudgetHolder :
  else :

I have two things to say about the above. Firstly, scripts in a language where leading whitespace is significant are very difficult to post to blogs. Secondly, I meant everything I said about the custom fields API. In my previous post, I complained about the Java standard library requiring double references – well here’s another example. Read the last ten lines and try to tell me that the developer in question was sober when he designed the interface.

This does exactly what I want (like all good sticky-tape solutions should). The only thing the JDVP did that annoyed me was to always render “Unknown” (or the localisation equivalent) in the case that one of my database fields contained NULL (some of our accounting codes have optional subcodes, for example). After discussions with the developer, I submitted a patch which made the NULL behaviour configurable, and he has included it in the latest release. Thanks, Wim.

Getting Jira to enforce a date field is in the future on issue creation

As part of a new Jira process I am developing, I need to ensure that the date stored in a certain custom field is in the future. I was using the “compare date and time” validator for this, checking to see that the value of the custom field was greater than or equal to that of the issue Created field. This was working well while I was using it on a standard workflow transition, but it bothered me that the user needed to create an issue and then immediately transition it in order for the validation to work. My users are a technical lot, but even they are likely to forget the second step of the process.

You can use validators on the Create Issue transition (if you can find it –  go to the initial step of your workflow and look for “incoming transitions”), but the technique I was using doesn’t work, as the Created field isn’t updated until after the validator is processed and I was thus comparing with Null. I have Misc Workflow Extensions, Jira Suite Utilities and Jira Toolkit installed, but none provided a validator that would compare a date field with anything other than another date field. Luckily I also have the Jira Scripting Suite installed, and I thought this would be a trivial use case. Grab the custom field data using a jython one-liner and compare with the system date.

It wasn’t so simple. Jira returns date custom field values as java.sql.Timestamp objects, which are nontrivial to compare with jython date objects. I then tried using java.util.Calendar instead of the native jython datetime library, thinking that a java.util.Date would be more easily compared with a java.sql.Timestamp because they implement the same interface. This is technically true, but I didn’t want to compare instantaneous times, only dates, and there is no native method for extracting a date-only component (as a Julian date, say) from a java.util.Date object. One might expect to be able to obtain the raw timestamp data and discard the fractional day components (say, by performing an integer division), but this falls foul of time zones.

Jira treats dates as timestamps with zeroed time-of-day components, but the database backend stores this as milliseconds since the Epoch, and this is what is returned in the Timestamp object. A bare date is thus stored as the timestamp of the immediately previous local midnight. In the case of Ireland in summertime, this will cause an off-by-one error in the algorithm if one naïvely performs an integer division by the number of milliseconds in a day. To find the correct number of local days since the Epoch, one must add the current timezone offset to both timestamps before discarding fractional days. The resulting algorithm is thus far from the desired one-liner:

from com.atlassian.jira import ComponentManager
from java.util import Calendar

cfm = ComponentManager.getInstance().getCustomFieldManager()
leavingDate = issue.getCustomFieldValue(cfm.getCustomFieldObject('customfield_10072'))
today = Calendar.getInstance()
tzoffset = today.getTimeZone().getOffset(today.getTimeInMillis())
leavingDateEpoch = (leavingDate.getTime()+tzoffset)//86400000
todayEpoch = (today.getTimeInMillis()+tzoffset)//86400000

if leavingDateEpoch < todayEpoch :
 result = False
 description = "Leaving date cannot be in the past"
 invalid_fields['customfield_10072'] = u"Leaving date cannot be in the past"

It works, but it’s damn ugly. I particularly love the double reference to the today object in line 7. How the Java standard library manages to be so verbose and still so lacking in basic functionality is beyond me. They actually seem to be going in the wrong direction – I found this wonderful piece of documentation on my travels:

int     Date.getTimezoneOffset()
Deprecated. As of JDK version 1.1, replaced by
-(Calendar.get(Calendar.ZONE_OFFSET) + Calendar.get(Calendar.DST_OFFSET)) / (60 * 1000)

Says it all, really.

Insecure by design

I came across an article today that lifted my spirits:

100% Verifiable Bug-Free Code Is Possible (Dobbs Code)

The executive summary: and have developed a microkernel that is provably correct, in defiance of the conventional wisdom that formal methods are only practical for the simplest of projects. While I take my hat off to the developers for their heroic efforts, I firmly believe this is only the first step in a process that will revolutionise the industry. The ultimate goal should be a complete, provably correct computing platform. This will not come about quickly or easily, but there are practical things we can do in the meantime.

Recently, the SANS Institute published a list of the 25 most dangerous programming errors. Most of these, e.g. buffer overflows, are rookie mistakes that every apprentice programmer is warned about, yet even with better training and increased collective experience, the population of errors in the wild seems to increase daily. The reason is simple: as the number of programmers grows, and their productivity increases, the number of opportunities for errors to creep in grows faster than the ability of the human mind to be vigilant. Or to paraphrase Murphy’s Law: if a programmer can make mistakes, he will make mistakes.

The conventional wisdom is to accept that such errors will be made, and be vigilant in testing. But no amount of post-facto investigation can give us 100% confidence that a catastrophic error doesn’t lurk somewhere in the code. With software increasingly responsible for people’s lives (fly-by-wire aircraft, nuclear power), the potential consequences of code errors will become unmanageable. Let me demonstrate.

The standard equation of risk analysis is

risk = probability × severity

What this means in practice is that in order to maintain risk below a given maximum, any event that has N times more severe consequences (e.g. a plane crash that kills 10 times more people than a car crash) should happen N times less often. But going from 99.999% (five nines) certainty to 99.9999% (six nines) is a lot harder than going from 99% to 99.9%, due to diminishing returns. Throwing man-hours of testing at such a problem does not scale.

Formal methods give us a way around this impasse. But we do not even need the expense of formal testing to eliminate the most common errors – design choices in our programming languages can do a lot of the work for little cost. Consider the state of the art before the introduction of structured programming in Algol-60. Without nested loops or multi-line conditions, the GOTO statement was king. GOTO-based programming languages are Turing-complete, in that they can perform any conceivable algorithm, but they are too flexible. It is quite possible (and easy) to write nonsense algorithms where loops would start or end inside the ELSE block of an IF statement, for example*. No modern programmer would contemplate such absurdities – there was a very good reason why GOTO statements were banished from polite society. And yet programming languages without GOTO statements are still Turing-complete.

What the above history lesson shows us is that, given sufficiently intelligent design paradigms, we can remove once-thought-necessary features from our lexicon without sacrificing Turing completeness, and thereby eliminate entire classes of potential programming errors.**

Now consider buffer overflow – this can be generalised to all kinds of array bounds violation; a buffer being merely a 1D array. The array index is constrained between two values, typically 0 and some integer N. If the algorithm attempts to access the array with an index outside this range, we have an array bounds violation. If this is not tested for explicitly by the algorithm (easy for a stressed programmer to forget) or implicitly in the execution environment (inefficient and not always enabled) undesirable behaviour can easily result. We could laboriously check every subscription operation in our algorithm to ensure that sane values were being passed at all times; or we could change our programming paradigm so that it is impossible to write an invalid subscription operation.

This is not as outlandish as it sounds – we already have a commonly-used language feature that does most of the work for us: FOREACH. A FOREACH loop iterates over the elements of an array, and automatically stops when there are no more elements. We cannot pass an invalid value into the array subscription operation, because there is no such operation; subscription is handled implicitly by the FOREACH. If all buffer operations used FOREACH statements, there would never be an overflow.

Now say that at some point in the near future we find similar, implicit, methods for array subscription that cover all sensible use cases (in the same way we found alternatives for all sensible use cases of GOTO). We could then eliminate the explicit array subscription operation from our lexicon, and buffer overflows would be a historical curiosity.

I think such a development is within reach. Like many programming geeks I have been working, on and off, for some time on a pet language project which, amongst other things, features strict limitations on the array subscription operator, as well as a plethora of implicit alternatives to handle common use cases. I haven’t yet been able to eliminate subscription completely, but all ideas would be gratefully received.

* This is a real example from personal experience, which shockingly did work but was (unsuprisingly) impossible to understand.
** Of course, if the language is still Turing-complete, it will therefore still be possible to make the same error; but you will have to go out of your way to deliberately do so., a match made in…?

Despite having played with Democracy Miro, I’m still rather attached to Azureus Vuze for one or two of its useful features*.

Being an addict of US scifi TV, I was excited to discover, which provides vodcast RSS feeds for most current popular US shows, such as my current favourites BSG and Lost. The killer advantage over other RSS sources (such as the excellent EZTV) is that one can subscribe to a particular feed in Miro or Vuze and get precisely one copy of every episode of that show. No more remembering to search mininova to see if the new episode was up yet! This was exactly what I had been waiting for since discovering Democracy Miro’s channels system.**

Of course, it didn’t take long for the system to break. Vuze’s RSS FeedScanner plugin would display a new episode in the list but not start downloading, instead giving a constantly shifting error message: “Init” > “Scanning 1/64…” >>> “Scanning 39/64…” > “Init” (it never seemed to get past 39). This would eventually time out saying “No data”. This affliction would only affect those particular episodes that feedmytorrents had sourced from mininova, but not those from the pirate bay (easily distinguished by the torrent URL). There was nothing wrong with the torrent file itself, as I could right-click > copy link URL and paste it into firefox, which would happily download the torrent and open it in Vuze, the default application. But of course this completely defeated the seamless experience.

I searched on the Vuze forums and found several similar problems reported but few solutions. One suggestion was that the setting “Use URL as referer” might need to be turned off. Sure enough, this worked. For whatever reason, it seems that mininova doesn’t like the HTTP referer field to be set to the “URL”, whichever URL that may be (itself?). Turning this option off (thus sending no referer) didn’t seem to break piratebay torrents (and why should it: this is the behaviour when one types in a URL by hand), so I disabled it on all my feeds. This makes me ask two questions. 1: why isn’t this option off by default and 2: what the hell does the HTTP referer field have to do with it anyway?

* coughcoughtorcoughcough! Interestingly, the latest version (4.1) of Vuze has reskinned itself to look almost exactly like Miro…
** sorry guys, I don’t watch Rocketboom…