On NaCl

Overview

Since I was introduced to the NaCl library, I've loved it. In the course of considering adding Salsa20/? and Poly-1305 support to OpenSSL, I thought I'd take a look at NaCl, since I knew it was based on those primitives as specified in Bernstein's papers.

Acknowledgments

Thanks to Bernstein for the NaCl library, Regher for his blog on software correctness and David Morris (qlkzy)  for his proof-reading skills and contributions.

Getting the Code

The code is public domain, and very small. However, I could only find mirrors of it in GitHub, and no obvious reference to the "current" release. The best I could do was a tar.bz2 referenced from the install page.

I didn't want to install it, only read the code! Please, please throw up a prominent link to the following:

• Source repository
• Documentation
• Issue Tracker

The OpenSSL project has all of these, despite being in the gutter in many other respects. They're not necessarily in a "prominent" place, and in the case of the documentation, they're incomplete.

Currently, simply pointing to http://hyperelliptic.org/nacl/nacl-20110221.tar.bz2 is insufficient, as it raises a couple of questions:

• Is this the latest release? If not, which is the latest?
• Why is it not distributed from somewhere supporting SSL/TLS?
• Why is it on hyperelliptic and not nacl.cr.yp.to as the rest of the site is?

These are minor things, but they are crucial to ensure confidence in the project, it's long-term survival, and that any one wishing to contribute can do so effectively.

Duplicate Code

Nothing too worrisome, but there are a few pieces of duplicate code. They're mostly utility functions like load_littleendian, and rotate. The drawbacks of writing code multiple times are well documented, and I don't know why Bernstein chose to duplicate the code (they're declared static) rather than pull them up into a utility library of some sort. Hell, given how short these functions are, not making them simply macros seems a little odd.

The methods I saw duplicated most often are marked static, and as pointed out by qlkzy, they're probably there to ease the compiler's job when in-lining functions.

Undefined Behaviour

There is at least one function used regularly throughout the source (and duplicated!) that could be considered to have undefined behaviour. I have copied it here from crypto_core/salsa20/ref/core.c:

static uint32 rotate(uint32 u,int c)
{
  return (u << c) | (u >> (32 - c));
} 

This function is used as part of a round for Salsa20, and it is only called with c with a fixed set of values, 7, 9, 13 and 18.

This is great, because if the compiler can figure out that it's possible set of input values never includes 32, great!

If, however, the compiler isn't so smart, then it may assume that c can be the full range of int, meaning that it is undefined on several values (most notably c = 32), meaning that it could be optimised to whatever the compiler feels like.

Regehr has an excellent blog post on this already, but for the general case, where the equivalent of c can be any value. In Salsa20, we don't need such generality.

There are a couple of potential fixes off the top of my head:

Use Regehr's Safe Rotate

Using the safe rotate proposed in Regehr's blog should alleviate these problems, but we don't actually need the generality.

There is also the issue that on older versions of Clang, his safe rotate is not recognised and optimised correctly, introducing some problematic performance issues

According to the log on Regher's bug, this has probably been fixed by now, and so could be safely used.

Define Multiple Rotate Functions

Define several functions, rotate_7(uint32 u), rotate_9(uint32 u), rotate_13(uint32 u), and rotate_18(uint32 u). for example:

static uint32 rotate_7(uint32 u)
{
  return (u << 7) | (u >> 25);
} 

Which would ensure that the compiler knows that the shift is never undefined. hopefully, a good compiler would aggressively inline these.

Define Macros

Defining a macro would give a couple of benefits:

• It could be put into a header file somewhere and used everywhere
• It would be inlined automatically by the pre-processor
• It can be made to avoid most forms of undefined behaviour

The macro would simply be :

#define ROTATE_7(u) (((u) << 7) | ((u) >> 25))

That would allow for a rotate-left by 7, avoiding any undefined behaviour and forcing the C pre-processor to inline it for you. These can be written once in a header file.

However, many C programmers do feel that macros are quite messy, and so would prefer to simply declare non-static utility functions in a header and use those, but copilers might not inline these, leading to an unacceptable performance penalty.

Ok Compilers

Once I got the code, I found a list called "okcompilers", posted here for completeness:

gcc -m64 -O3 -fomit-frame-pointer -funroll-loops
gcc -m64 -O -fomit-frame-pointer
gcc -m64 -fomit-frame-pointer
gcc -m32 -O3 -fomit-frame-pointer -funroll-loops
gcc -m32 -O -fomit-frame-pointer
gcc -m32 -fomit-frame-pointer
spu-gcc -mstdmain -march=cell -O3 -funroll-loops -fomit-frame-pointer -Drandom=rand -Dsrandom=srand
spu-gcc -mstdmain -march=cell -O -fomit-frame-pointer -Drandom=rand -Dsrandom=srand

This has the really bad effect of tying yourself to a given set of compilers and flags. This means that you won't get any new features or tooling from newer compilers (e.g. Clang with Valgrind) and that those who don't have access to the specified compilers will not feel at ease when building the source.

Access to the latest and greatest tooling is often critical for tracking down bugs, memory leaks, etc.

Will it break, won't it break should not be in my mind when I'm building with a different, but still standards compliant, compiler.

There is also the issue of knowing exactly which flags are required for performance, and which are required for security. What happens if I can't use -funroll-loops, does this break the performance, or does it affect the timing invarience of  the algorithms? What about -O3, is that only for performance purposes? This is about as clear as mud.

Non-Standard Build

The installation proceedure recommends I use the "./do" command to build the source. Just use Make, we all know how to use it. It's standard, well understood and easily extensible.

I wouldn't normally advocate Make, but something is better than nothing, and for a small project like this, I don't think it would need anything more advanced than Make.

Supplying Assembler Alternatives

This seems like a good idea at first, you can hand optimise the assembler better than a compiler, and in the case of C, avoid undefined behaviour! Win!

However, these are static blobs in comparison to C code. C code inherits a lot of benefits from compiler development. For example, I don't think you'd be able to do anything with the assembler blob and valgrind or ctgrind.

You also can't hand optimise better than a compiler, not any more. And while attacks only get better, compilers only get more aggressive optimisations.

Conclusion

I love the idea of the NaCl library, but I think for it's long-term survival, it needs to pull up it's "administrative socks" as it were. Potential undefined behaviour should be a huge no-no in cryptographic software, and standard software engineering practices; such as a standardised build system, version control, and so on; should be a given

I would hate for such a fantastic library and concept to disappear or fall by the wayside because of such trivial issues.

Google+ Deception

Overview

Google+ is deceitful and I consider it to be harmful.

Blogger and Google+

Obviously, I use blogger (Or is it blogspot?) for blogging. I have a couple of blogs, and I update them reasonably frequently.

I was recently prompted on one of my blogs to start integrating with Google+ which is something that I would not want. I found the message to be difficult to follow at first glance, and couldn't see easily how to decline the offer.

Fast forwards to today, and both of my blogs had at some point gone from simply prompting me to share on Google+ to simply posting automatically. This is unwanted behaviour, as I do not wish to use Google+, or any social network for that matter.

I do not want to "self-promote" my personal blogs and spam my friends. If they want to read my blog(s), they will do so without me spamming them.

Worse still, do not take the choice to spam people I know on the social network I don't want to use away from me. I didn't choose to use Google+, I didn't choose to spam those people.

Google, please, for the love of all that is holy, please stop trying to force everyone to be a Google+ user. It's like the creepy guy with the beat-up van with "Free Candy" hand written on the side. No one wants what you're offering, and everyone knows that it's the old bait-and-switch. Just stop.

PPUK Reform

Overview

The Pirate Party UK (PPUK) is a political party in the UK, who typically fight for civil liberties, copyright reform and a more transparant government. Full disclosure, I'm a full, membership-paying member of PPUK.

This is not a reform proposal in the traditional sense. This is a look at how PPUK acts and is perceived, and if that can be altered to be more of a positive. Think of it as a perspective reform.

Where we're at

Historically, we've taken on campaigns at both the local and national level. We should keep on doing this, as both levels are required to effect our goals.

However, our campaigns have almost always been in opposition to something, for example, we opposed the withdrawal of Legal Aid, we opposed the detention of Chelsea Manning, the "snooper's charter", and so on.

When it comes down to it, we expend a disproportionate amount of energy saying "no" to our opponents. We often celebrate in the defeat of our opponents. This gives the impression to the public (well, those that know about us, that's a whole other blog post) that we are adversarial, and against progress.

We need to acknowledge that the stated goals of these schemes may have merit, bring substantial benefit to the public (ex. care.data), and even that they may align with our goals -- but that the proposed implementation has issues; we need to offer alternatives which still support the goal.

Further to this, we don't provide anything to the public -- no tools for activists, we currently have little in the way of getting up and running in a local area, how-tos for running a campaign, nothing.

The Future?

I feel that, once we're a larger organisation, it would be most helpful for us to conduct ourselves in a way that is consistent with the goals and principles laid out in our manifesto. Beyond that I feel that we should be aiming to improve our society.

I think that this means, instead of simply opposing problems, (e.g. pharmaceutical greed, violation of civil liberties, invasion of privacy, etc.) we must support alternative solutions.

The simplest one from that list is the invasion of our privacy -- we can support projects that improve people's privacy online (e.g. HTTPS Everywhere, TOR, GnuPG). We can provide infrastructure, many of our volunteers have skills they could offer (programming, design, UX, etc.), providing them with more public support and exposure, building our own complementary tools, educating people in their proper usage, and so on.

Personally, I feel that one of our most lacking areas is public education. We have so much knowledge, yet we consistently fail to share it.

At our most recent branch meeting, I was asking about how many members we have, and the numbers I got back varied from 300 to 700. I also happen to know that the number who voted in our most recent NEC elections was a mere 57 people for one of the posts. I am strongly of the belief that this is due to disaffection in our own ranks from to our perceived (and, in some cases actual) lack of action. We must do; the future is not opposed, the future is built.

The Security of the Proposed care.data Scheme

Overview

Ceri the Duck has a blog post titled "Care.Data – why I am happy for my medical records to be shared for research". In this post, they make the argument that under the care.data scheme, data protection would be improved for patients.

In this post, I will tackle this misconception, which revolves around two core arguments; firstly that there will be limited access to identifiable information, and that the care.data scheme will provide a better security framework to work within.

No Identifiable Information

"care.data will only provide access to ‘potentially identifiable’ information"

If we look at the HSCIC price list, we see that they provide an extract of data "containing personal confidential data".

Even if this data has names, and other directly identifiable data stripped out, we know that anonymised data can be de-anonymised almost trivially (Further reading from Light Blue Touchpaper) in the vast majority of cases.

A Better Security Framework

"I am much happier with the level of data security care.data will provide than with the current ad-hoc arrangements. They will be consistent, with good oversight, the information disclosed will only be what is needed instead of having to comb through a patient’s full record, ..."

This is simply not true. The care.data scheme will be taking medical records from a setting where they are hard to even sort through with legitimate access (as pointed out by the author themselves) to a situation where the records will be much more easily accessible to many thousands of people, none of whom will have undergone any serious training into information security, data protection laws, or the ethical issues surrounding the use and dispersal of this data. It is also highly unlikely that they will have had so much as a criminal record background check.

Granted, the current situation is very poor, but it does not allow for a large scale abuse of the system. Sure, I could target Bob Smith, break into his doctor's surgery and steal his record. With the new system, I could target large swathes of the population by simply bribing the right people. The information gained could be used by all manner of people, be it for surreptitious back ground checks on potential dates, to discrediting a political candidate, and everything in between.

And that's just bribing-based attacks. Think of the rubber hose cryptanalysis opportunities, the social engineering based attacks, physical security attacks, phishing and spear phishing attacks, attacks on end-point security (this is your classical "hacking into the computer" attack), and so on.

Data transfer must occur at some point, and with great data transfer comes great opportunity. How do you conduct the transfer of data, and how do you setup the transfer so that you're definitely sending the data to the person(s) you think you are? These are generally considered to be solved problems in the cryptographic community for the most part (key distribution is hard, for instance), but in practice, it is anything but.

In short, this centralisation effectively paints a massive target on the back of the country's medical records, and gives access to institutions with some of the worst information security going in many places.

The adversaries in this situation will not be small time. Computer crime is big business, and aside from nation states, organised criminals are one of the hardest adversaries to defend against. They are extremely well organised and well funded, with extensive experience attacking high value targets. Once they've breached the system, they have the contacts in to sell the data on and actually turn a profit on this kind of attack.

Conclusion

Security is far harder than most people think, and most people don't know how much they don't know. HSCIC cannot be in the position of implementing this system and not be aware of the serious and numberous risks outlined.

The care.data scheme will suffer a breach, and given how centralised the system is likely to be, I expect the breach to be a large and very serious breach of previously unheard proportions.

New care.data leaflet

Overview

There is a new scheme called "care.data", which will cause previously confidential medical records to be sent from a person's GP surgery to a central database.

Access to this database will then be sold for a fee.

The process of informing the public that their confidential medical records will become a commodity for those who meet the criteria for accessing the records has been spotty at best, and down right misleading at worst.

Leaflet

We (my partner and I at least) will be hitting the streets to distribute an A5 leaflet to the general populace informing them that this is taking place.

This leaflet is licensed CC-BY-4.0, meaning that you are feel to remix, reuse and redistribute as you please, as long as you attribute my partner and I.

You can access the full files: SVG, PNG and PDF. If you feel that this is an important issue, the leaflet is quite amenable to cheap risograph printing, so get yourself a print run done, and get out there on the streets!

The Bet

Overview

 I have entered into a bet with my other half.

The bet is simple. That I can get her to the point where she is capable of running a half marathon in 6 months. She can't run a 5K yet.

About Me

I am what I would think of as "normal". But my parents are unsure of where I get my drive to exercise, my other half seems to see my as some sort of superman, often using words like "inspirational" and "incredible".

Truth be told, I am not a superman, I'm just a guy who happens to do a little bit of running on the side. I've run in a couple of 5Ks, a 10K, a couple of super sprint triathlons (if you're curious, it wasn't quite a super sprint, it was a 400m swim, a 20km ride and a 5km run) and a sprint triathlon (Usual distances).

I do not think of my self as particularly sporty, I'm between 56kg and 58kg depending on when I last ate, and I stand about 1.8m tall.

My History

When I was quite young, I swam. I swam a lot, I got my "honors" badge for swimming before I was in year 7, meaning I swam something like 1km in 40 mins, and in that same session, I extended it to 1.5km to get my 1.5km badge. Nothing like two birds with one stone. I eventually went on to swim for my city in my age group for a year or two, but eventually stopped when I went into senior school. At the time I thought I would be getting lots of homework, but looking back, I really don't know why I stopped -- I knew I wasn't the sort of person to actually do my homework.

Outside of that, I didn't really do sport, and I certainly didn't run. Even doing the breaststroke gave me issues with my knees. At school, we were made to do rugby and cross country running, where my knees were a serious issue. A bad tackle could cause my knee to dislocate, meaning that I'd be stuck squelching in the muddy ground clutching my leg until taken somewhere so that I could fix my knee. It was unpleasant. Cross country running was better, but it caused my knees to hurt a lot, so I ran very slowly. Slower than the over weight guys with asthma.

When I made it to sixth form, we were allowed to choose a sport. I chose badminton, which I knew I'd excel at from doing PE in previous years. I did do very well, often taking on the teacher and actually managing to put up a not-unreasonable fight, but always eventually losing. It was rare for me to lose to my peers.

After that, I went to university, I mostly stopped doing anything sport related in my first year, but my my second year, I'd been invited to come along to a pole exercise session, which I wasn't entirely awful at! I ended up performing at the university "woodstock", and teaching for a couple of years, so I didn't do too badly out of it.

Once I left university, I kept teaching at pole, but also took up running and entered a few triathlons. They were good fun, to say the least! After a couple of triathlons, I joined up with the Jitsu club and promptly put my back out.

After a year and a bit recovery, I was back on the mat, and back to running, but with not nearly as much dedication as I had before. I intend to go back to pole sooner or later, but I don't know when.

The Bet

While in the kitchen with my partner the other evening, our conversation turned to exercise. My other half does not consider herself sporty at all. I made the passing comment that if she gave herself over to me, I could probably have her running a marathon with around 6 months of dedicated training.

Obviously, she didn't believe me, and after a bit of cajoling and back and forth, we entered into a bet that I could have her running a half marathon in 6 months.

I've never run a half marathon, in training or otherwise, but I know what it, theoretically, takes to get there. I like a challenge.

My partner has a large mitigating factor that we need to deal with. She has quite a serious anxiety disorder, meaning that panic attacks in public, and extreme self consciousness are two of our biggest hurdles. Without that, I'd say us just agreeing to stop would be our biggest hurdle. She can do the running, she just doesn't believe that she can.

The First Run

The first run started out more difficult, since letting her keep pace and running side-by-side is quite difficult, especially since I have much longer legs, my natural pace is a bit higher than hers, so I started to pull away, leading to me upsetting her, with her saying that I was leaving her behind,

After she was warmed up, and I kept running a pace or two behind to make sure I was matching her pace, we managed to keep the run going, by simply running for 2 lamp-posts' distance, and then walking the same amount. She even said that while walking she was feeling lazy, because we weren't running!

Unfortunately, during the walk part of our run, a vicar, cheerfully invited us to worship with his parish. I thought that it was a lovely gesture, but he wouldn't be doing so if he knew what I thought about his god. I politely declined, keeping my cool and walking straight on. We would have to run back that way. We did another run section shortly afterwards, and turned round. After a brief walk, we were about to set off again with more running, but I needed to help my other half not freak out about being "Jesus at" if I could so verb my nouns. We got past this, and ran straight past the vicar with no offers of Jesus or other religious figures being politely sent our way.

When it came for the last run, I said that she should run for as long as she could. Before I could finish my sentence, I'd caused a panic attack, what I'd wanted to say was that, between where we where and home, she should run as much of it as she comfortably could, then walk the rest.

Once we'd managed to fix the panic attack, say the right words, we got back on our way. She managed to run all but about 5 meters of the rest of the distance back home (proving to me, but not to her, I think) that she can run for longer than she thinks.

I'm looking forwards to running more with my partner.

Tools of the Trade

We both have Fitocracy for logging our exercise, and our diet is quite simple. We're on our way to being vegetarian, and we explicitly avoid foods that are very high in carbohydrates. I'm looking at you pasta and rice. I think a plant-based diet will really help us in this.

Combined with these blogs and our fitocracy, we should be able to plot our course when we look back at this.

Searching with Bloom Filters in Haskell

Overview

This post is primarily about my experience with the bloomfilter package in Haskell.

Coding it up

Coding it up was much of a muchness, aside from a late realisation that there's no Hashable instance for Text which caused a quick change from Text to ByteString, but aside form that, it was very easy.

Even querying the index is easy, I shall post up the code when I am back at home, since I'm with my parents over the Christmas period.

Overall, it's roughly 38 lines, but around 7 lines of that are simple module imports.

Testing

To test it, I grabbed roughly 2.5MB of data from Project Gutenberg, and simply started querying the index. I haven't done any "proper" performance testing so I've just been feeling it out with no timers.

I didn't bother forcing anything, so the first query can take a little while as the index is built, but it's nothing prohibitive. After that, every search feels instantaneous.

After building with -rtsopts, I had it generate a heap profile, which showed that the peak memory allocated with my test set was roughly 8MB, but that fell back down quite rapidly.

Improvements

I suspect that a carefully used deepseq, and ByteString.Lazy could really improve the memory foot print of the system, and remove the initial "hang" when doing the first search. I shall have to investigate this at a later date.

Extensions

If I could just get access to the underlying UArray Int Hash in a way that I could manipulate, I could make searching more probabalistic, but also much faster.

Similarly, I could extend the usage of a bloom filter into a similarity metric, but unfortunately, I'm not entirely sure how to use the underlying representation at this time.

I basically need access to the cardinality of the underlying representation, and the ability to union and intersect the underlying bit arrays. Once I have these (or worked out how to do it on the underlying representation) performing similarity matching becomes very simple.

Conclusion

Haskell's bloom filter library seems to be very fast whilst maintaining an easy to use facade.

However this is not flexible enough to really play with bloom filters in all the ways they can be very easily. Perhaps basing the underlying representation on the bitset package, or offering a "serialisable" version which can be easily manipulated would be all it takes.