A stained glass puzzle

Chaos and Order

Photo by MattClarke @ StackExchange, cc by-sa 3.0

Here’s an interesting puzzle set by user MattClarke at the Stack Exchange puzzling website. The stained glass window you see here is called Chaos and Order. You simply have to figure out why.

I found the answer to this yesterday, but don’t go peeking before you’ve had a crack at it yourself!

If you’re really stuck, try looking for a link to the answer at the end of this sentence. It’s there somewhere.

Posted in fun stuff Tagged with: ,

Frack off, it’s none of your business

Earlier this year, the UK government published a report on the effect of shale gas mining (i.e. “fracking”) on rural economies (link to PDF document). One can only assume that their findings were not very positive, because most of this document has been censored, and they’re not telling us why. Even the author’s name has been replaced with the word REDACTED.

For example, here is section 4 of the document, in its entirety:

Section 4: Conclusion

This report has examined the potential economic, social and environmental impacts that are likely to be associated with an expansion in shale gas exploration. REDACTED

To a large extent these effects are already experienced by those rural communities located near established extraction activities e.g. quarrying, mining and conventional gas extraction.

REDACTED

REDACTED

REDACTED

Current proposals from both government and operators appear to be following a similar approach. Under the commitments of the UK Onshore Operators’ Group (2013), shale gas exploration could provide a community contribution of £100,000 per hydraulically fractured site as an initial benefit, equivalent to total UK payments of between £3 and £12 million. Meanwhile, the government recently announced that English councils which give the go-ahead to shale gas developments will be allowed to keep 100 per cent of the business rates they collect from consented sites. This is estimated to be worth up to £1.7m a year for a typical site.

REDACTED

REDACTED

REDACTED

REDACTED

REDACTED

REDACTED

REDACTED

REDACTED

REDACTED

REDACTED

REDACTED

REDACTED

I was fairly ambivalent about fracking before I saw this, but now its quite clear that the people behind it are a bunch of faceless REDACTED who have got Whitehall stuck so far up their REDACTED that they can’t even REDACTED REDACTED

REDACTED

(via UsVsTh3m)

Posted in rant Tagged with:

Project Euler hacked

Project Euler has been taken down after a security breach. There is no indication of when — or even if — the site will return. All that’s left is the following message:

project-euler-offline

What sort of lowlife scumbag would attack a site like this?

Posted in rant Tagged with:

HackerRank W3 — where was everyone?

The latest HackerRank weekly challenge attracted 71 entries from the US and 387 from India, but only four from the UK. I think this is the lowest turnout so far. Maybe the good weather had something to do with it.

But anyway, I’m still quite pleased with coming in 1st out of the UK contingent and 52nd (out of 720) overall. My solution to the GCD product question could have been speeded up, and I would probably have made the effort if my first solution hadn’t passed all the test cases in a matter of milliseconds.

Oh well.

Posted in hacks Tagged with: , ,

Untrusted

Untrusted is a Javascript adventure game where the only way you can win is by rewriting parts of its source code as you go along. For example, in the very first level, your character (a simple “@” character) is imprisoned inside four walls (represented by “#” characters). To reach level 2, you have to edit the code that creates the walls. Simply deleting it will do the trick, as shown here:

Untrusted, level 1

But it soon gets much more complicated. There are 22 levels in all — level 22 just displays the end credits, but it took me a little while to figure out how to get there. The game’s backing music is quite good, too.

Try it for yourself.

(via UsVsTh3m)

Posted in fun stuff Tagged with: , , ,

CipherSaber

I recently learned about an encryption protocol called CipherSaber, which was developed in 2001 by author, consultant and Star Wars fan Arnold G. Reinhold in retaliation against government plans to restrict access to strong cryptographic techniques.

CipherSaber is based on a stream cipher called RC4 (a.k.a. “Arcfour”) that was developed by Ron Rivest. Since the RC4 algorithm is simple enough for a programmer to implement from memory, it is effectively immune to any sort of software embargo.

Although CipherSaber lacks important features like a key exchange mechanism and cryptographic techniques have moved on since 2001 (RC4 is no longer considered entirely safe), CipherSaber is still a useful cipher of last resort. I’d encourage anyone with an interest in cryptography or programming to try their hand at creating their own implementation. Reinhold’s pages are starting to show their age (broken links everywhere!), so I’ll summarize the algorithm below:

CipherSaber Algorithm

Ingredients

You will need:

  • A secret key (up to 246 bytes)
  • Binary data to be encrypted or decrypted (as many bytes as you like)
  • A number num_rounds which should equal 1 for the original CipherSaber algorithm, or 20 for CipherSaber-2 (recommended). Or you can choose some other value if you like.

Method

  1. Create two 256-byte arrays called S and S2.
  2. Initialize S by filling it with all the values from 0 to 255 (i.e., S[0]=0, S[1]=1, S[2]=2, and so on.)
  3.  Copy the secret key to the bytes at the start of S2.
  4. If you’re encrypting, you should then generate ten bytes of random data (called the initialization vector). Write a copy of these ten bytes to your output file. If you’re decrypting, read these ten bytes back in from the start of the binary data.
  5. Append the initialization vector to S2, directly after the secret key. Then fill up the remainder of S2 by repeating the secret key and initialization vector until you have set all 256 positions in S2.
  6. Now we have to randomize the contents of S based on the contents of S2. This is done by swapping bytes in S according to the following method, using the value of num_rounds you chose earlier:
    j = 0
    for n in (1 .. num_rounds)
        for i in (0 .. 255)
            j = (j + S[i] + S2[i]) mod 256
            swap S[i], S[j]
        end
    end

    You can now discard S2; it won’t be used any more.

  7. Use S to generate a pseudo-random stream of bytes to combine with the input data (using exclusive-or (XOR) operations). Since this is a symmetric cipher, the procedure is exactly the same for encryption and decryption:
    i = 0; j = 0
    for each byte b of binary data:
        i = (i + 1) mod 256
        j = (j + S[i]) mod 256
        swap S[i], S[j]
        k = (S[i] + S[j]) mod 256
        output (b xor S[k])
    end

Well I hope that isn’t too complicated. Frankly it’s about at the limit of what I’d be able to reproduce from memory, and I’m not sure I’d be able to get it right first time either. But do have a go at writing your own. You’ll probably want somewhere to test your code, and for that purpose I’ve set up an online encryption/decryption tool that you’re welcome to use.

And finally, don’t forget to use a strong password with CipherSaber. Here’s a text encrypted with CipherSaber-2 using one of the 25 most common passwords of 2013. See if you can figure out what it was:

f8 a2 76 5d d2 3a 75 67 0f 15 ea 1e 8d 55 9f 39 69 cd 3f d6 61 48 06 85
65 1e a3 1a eb d7 88 dd d8 cd 46 e8 0c d6 cd 2d b1 bf 7b 34 aa fc aa ed
39 a9 14 6f e7 5c 57 f6 23 f8 69 d3 17 f7 0a f8 a8 7d 29 f3 9c e7 45 51
0d 6c 92 b8 9f 3d 6c 5a c8 8c 7d 71 e0 60 75 fb 00 61 c6 f2 02 60 e3 38
ab c0 48 f7 ed bd 05 67 c0 25 99 cc 85 67 23 ae 67 61 e2 0c ce 90 95 c8
8a 9f 19 ca 2e 35 0b a8 c3 31 6a 39 3a 24 52 31 e4 81 ae 35 f6 d9 c7 5f
31 3e 6f 2f 2f 96 87 95 0c 2f 90 87 1f a2 94 68 e3 ac 93 29 4d a7 53 24
a1 ca 51 35 10 84 50 58 01 12 42 6a 6a 0b f4 1d a6 33
Posted in cryptography, hacks Tagged with: ,

Unlocking a car with your brain

A marvellous bit of science here from professor Roger Bowley:

Posted in youtube Tagged with: ,

How Slartibartfast got his name

At half past ten tonight (about ten minutes from now) it will be exactly 36 years since the first episode of The Hitchhiker’s Guide to the Galaxy was broadcast. To mark the occasion, the BBC is not only repeating the entire series on Radio 4extra, but has also published some clips from other programs where the series was discussed. Here’s one where Douglas Adams describes how he arrived at the name Slartibartfast for one of the characters:

Posted in fun stuff Tagged with: ,

Wolfram Language

I don’t think I’ve ever found the arrival of a new programming language worth getting excited about. But this really does look interesting:

If anyone ever gets round to creating a real Hitchhiker’s Guide to the Galaxy, this is the sort of language they’ll be using.

Posted in youtube Tagged with: , ,

Subpixel-aware image scaling

Close-up view of an LCD monitor showing the letter "e" rendered with (top) no antialiasing, (middle) traditional antialiasing, and (bottom) subpixel antialiasing. (Credit: ALexL33 @ Wikimedia Commons)

Close-up view of an LCD monitor showing the letter “e” rendered with (top) no antialiasing, (middle) traditional antialiasing, and (bottom) subpixel antialiasing. (Credit: ALexL33 @ Wikimedia Commons)

Subpixel rendering is the technique your computer uses to make text on the screen as readable as possible even at small font sizes.

In a typical LCD monitor, each pixel is represented by a combination of three separate light-emitting elements, which are coloured red, green and blue. When they are all switched on, the pixel appears white, and when they are all switched off, the pixel appears black. Other colours can be displayed by varying the red, green and blue components individually, and for shades of grey, these components are always equal.

To display smooth lines and curves, a technique called antialiasing is used to eliminate the jagged edges that appear where dark and light pixels are placed adjacent to each other. This is illustrated in the middle of the image on the right, where the pixels forming the letter “e” have been changed to smoothly varying grey levels to avoid the jagged appearance of the non-antialiased letter at the top of the image.

Subpixel antialiasing goes one step further by working on the transitions between individual light-emitting elements instead of at the pixel level. This is done by applying a reddish or bluish hue to pixels to adjust the brightness at the edges of each RGB pixel.

After reading a recent question at Stack Overflow, I got to wondering how easy it would be to reverse this subpixel rendering process on antialiased text. This might, for example, be useful if you’re trying to use OCR software to read text from a screenshot image.

Here’s an example of text grabbed from my computer monitor (scaled up 300%):

Screen grab of antialiased text

If you look closely, you can see that the letters are coloured red on the left and blue on the right due to the effects of subpixel antialiasing:

Subpixel antialiasing

OCR software often uses thresholding to separate text from background details. Applying a simple 50% threshold filter to this antialiased text gives illegible results:

Thresholded text

Although this can be improved by choosing the threshold value more carefully, I got much better results by writing some software to scale up the original image while taking subpixel antialiasing effects into consideration. This is what I got:

Thresholded text after smart scaling

If you think it might be useful, you can download the software here: subpix.c. It uses the GD graphics library, but it shouldn’t be too hard to make it work with other libraries.

Posted in graphics, hacks Tagged with: