Beyond Conway: Cellular Automata From All Walks Of Life

November 1, 2017 by Christian Trapp 24 Comments

There’s a time in every geek’s development when they learn of Conway’s Game of Life. This is usually followed by an afternoon spent on discovering that the standard rule set has been chosen because most of the others just don’t do interesting things, and that every idea you have has already been implemented. Often enough this episode is then remembered as ‘having learned about cellular automata’ (CA). While important, the Game of Life is not the only CA out there and it’s not even the first. The story starts decades before Life’s publication in 1970 in a place where a lot of science happened at that time: the year is 1943, the place is Los Alamos in New Mexico and the name is John von Neumann.

Recap: What is a CA?

The ‘cellular’ part in the name comes from the fact that CAs represent a grid of cells that can be in a number of defined states. The grid can have any number of dimensions, but with three dimensions the visual representation starts to get into the way, and above that most human brains stop working, so two-dimensional grids are the most common — with the occasional one-dimensional surprise. The cells’ states are in most cases discrete but a subset of continuous CAs exists. During the operation of a CA the future state of every cell in the grid is determined from each cells state according to a set of rules which in most cases take into account the states of neighboring cells.

Continue reading “Beyond Conway: Cellular Automata From All Walks Of Life” →

10 Year Old Bug Crushed By Hacker On A Mission

October 31, 2017 by Christian Trapp 11 Comments

PCI pass through is the ability of a virtualized guest system to directly access PCI hardware. Pass through for dedicated GPUs has just recently been added to the Linux kernel-based virtual machine. Soon afterward, users began to find that switching on nested page tables (NPT), a technology intended to provide hardware acceleration for virtual machines, had the opposite effect on AMD platforms and slowed frame rate down to a crawl.

Annoyed by this [gnif] set out to to fix the problem. His first step was to run graphics benchmarks to isolate the source of the problem. Having identified the culprit in the GPU, [gnif] began to read up on the involved technology stack. Three days of wrapping his head around technical docs allowed [gnif] to find the single line of code that resulted in a faulty memory set up and to implement a basic fix. He then passed the work on to [Paolo Bonzini] at patchwork.kernel.org, who released a more refined patch.

The bug affecting PCI pass through had been around for ten years and had received little attention from the manufacturer. It gained prominence when graphics cards were affected. In the end it took one very dedicated user three days to fix it, and then another day to roll out a patch for Open Source operating systems. In his notes [gnif] points out how helpful AMDs documentation was. With the right to repair in debate, DRMed technical docs and standards locked behind paywalls, [gnif]’s story is a reminder of the importance of accessible quality documentation.

Interactive Visual Programming With Vvvv

October 26, 2017 by Christian Trapp 11 Comments

Did you ever feel the urge to turn the power of image processing and OCR into music? Maybe you wanted to use motion capture to illustrate the dynamic movement of a kung-fu master in stunning images like the one above? Both projects were created with the same software.

vvvv -pronounced ‘four vee’, ‘vee four’ and sometimes even ‘veeveeveevee’- calls itself ‘a multi purpose framework’, which is as vague and correct as calling a computer ‘a device that performs calculations’. What can it do, and what does the framework look like? I’d like to show you.

Since its first release in 1998 the project has never officially left beta stage. This doesn’t mean the recent beta releases are unstable, it’s just that the people behind vvvv refrain from declaring their software ‘finished’. It also provides an excuse for some quirks, such as requiring 7-zip to unpack the binaries and the UI that takes some getting used to. vvvv requires DirectX and as such is limited to Windows.

With the bad stuff out of the way, let’s take a look what vvvv can do. First, as implied by the close relationship with DirectX, it’s really good at producing graphics. An example for interactive video is embedded below the break. With its data flow/ visual programming approach it also lends itself to rapid prototyping or live coding. Modifications to a patch, as programs are called in this context, immediately affect the output.

The name ‘patch’ harkens back to the times of analog synthesizers and working with vvvv has indeed some similarities with signal processing that will make the DSP nerds among you feel right at home.

Continue reading “Interactive Visual Programming With Vvvv” →

DUHK: Don’t Use Hard-Coded Keys

October 25, 2017 by Christian Trapp 31 Comments

The title reads like the name of a lecture in cryptography 101 or the first rule of Crypto Club. ‘DUHK‘ is in fact neither of those but the name of a recently disclosed vulnerability in a pseudorandom number generating algorithm (PNRG) that was until recently part of the federal standard X9.31.

Random numbers are essential to viable cryptography. They are also hard to obtain leading to solutions like using the physical properties of semiconductors or decaying matter, that are governed by quantum effects. The next best solution is to log events that are hard to predict like the timing of strokes on a keyboard. The weakest source of randomness is math, which makes sense, because one of maths most popular features is its predictability. Mathematical solutions have the one redeeming quality of being able to produce a lot of numbers that look random to a human in a short time.

PNRGs require a starting point from which they begin to produce their output. Once this seed is known the produced sequence becomes predictable.

The X9.31 PNRG is an algorithm that is used in various cryptographic algorithms and has been certified in the Federal Information Processing Standards for decades until it was dropped from the list of approved standards in 2016. The researchers behind DUHK found out that the standard allowed the seed to be stored in the source code of its implementation. The next step was to look for software that did this and they found X9.31 in an older version of FortiOS running on VPN gateways.

Should I be Worried?

Probably, maybe not. The analysis (PDF) published by the team behind DUHK notes that the vulnerability is limited to legacy implementations and doesn’t allow to takeover the device running them, only to eavesdrop on ‘secure’ connections. The scope of this is much more limited than exploits like remote code execution via bluetooth. It is on the other hand providing a strong case for handling standards and technical certifications with extreme scrutiny. The teams conduct also gives insight into the best practises for white-hat hacking which are frequently discussed around here. And they have a great theme song.

Solving Mazes With Graphics Cards

October 23, 2017 by Christian Trapp 16 Comments

What if we told you that you are likely to have more computers than you think? And we are not talking about things that are computers while not looking like one, like most modern cars or certain lightbulbs. We are talking about the powerful machines hiding in your desktop computer called ‘graphics card’. In the ordinary gaming rig graphics cards that are much more powerful than the machine they’re built into are a common occurrence. In his tutorial [Viktor Chlumský] demonstrates how to harness your GPU’s power to solve a maze.

Software that runs on a GPU is called a shader. In this example a shader is shown that finds the way through a maze. We also get to catch a glimpse at the limitations that make this field of software special: [Viktor]’s solution has to work with only four variables, because all information is stored in the red, green, blue and alpha channels of an image. The alpha channel represents the boundaries of the maze. Red and green channels are used to broadcast waves from the beginning and end points of the maze. Where these two waves meet is the shortest solution, a value which is captured through the blue channel.

Despite having tons of cores and large memory, programming shaders feels a lot like working on microcontrollers. See for yourself in the maze solving walk through below.

Continue reading “Solving Mazes With Graphics Cards” →

The Grafofon: An Optomechanical Sequencer

October 23, 2017 by Christian Trapp 4 Comments

There are quick hacks, there are weekend projects and then there are years long journeys towards completion. [Boris Vitazek]’s grafofon falls into the latter category. His creation can best be described as electromechanical sequencer synthesizer with a multiplayer mode.

The storage medium and interface for this sequencer is a thirteen-meter loop of paper that is mounted like a conveyor belt. Music is composed by drawing on the paper or placing objects on it. This is usually done by the audience and the fact that the marker isn’t erased make the result collaborative and incremental.

These ‘scores’ are read by a camera and interpreted by software.This is a very vague description of this device, for a reason: the build went on over six years and both hard- and software went through several revisions in that time. It started as a trigger for MIDI notes and evolved from there.

In his write up [Boris] explains the technical aspects of each iteration. He also tells the stories of the people he met while working on the grafofon and how they influenced the build. If this look into the art world reminds you of your local hackerspace, it is because these worlds aren’t that far apart.

Continue reading “The Grafofon: An Optomechanical Sequencer” →

Exploiting Weak Crypto On Car Key Fobs

October 18, 2017 by Christian Trapp 55 Comments

[tomwimmenhove] has found a vulnerability in the cryptographic algorithm that is used by certain Subaru key fobs and he has open-sourced the software that drives this exploit. All you need to open your Subaru is a RasPi and a DVB-T dongle, so you could complain that sharing this software equates to giving out master keys to potential car thieves. On the other hand, this only works for a limited number of older models from a single manufacturer — it’s lacking in compatibility and affordability when compared to the proverbial brick.

This hack is much more useful as a case study than a brick is, however, and [tomwimmenhove]’s work points out some bad design on the manufacturer’s side and as such can help you to avoid these kind of mistakes. The problem of predictable keys got great treatment in the comments of our post about an encryption scheme for devices low in power and memory, for instance.

Those of you interested in digital signal processing may also want to take a look at his code, where he implements filtering, demodulation and decoding of the key fob’s signal. The transmission side is handled by rpitx and attacks against unencrypted communications with this kind of setup have been shown here before. There’s a lot going on here that’s much more interesting than stealing cars.

[Via Bleeping Computer]

Continue reading “Exploiting Weak Crypto On Car Key Fobs” →