New Location

As of September 7th, 2013 this blog will be moved to http://onehourhacks.com!

Simple Credit Card Validator

Validating credit cards numbers is a fairly simple job, and there are no short supply of algorithms out there you can easily download to do it. That being said, it is a perfect algorithm to write in Haxe for the following reasons:

• Speed isn't super critical
• It doesn't involve the system in any way
• You can use the same code across PHP, JS, Java, C++, C#, Actionscript etc.
• The same code would be useful in all contexts.

Algorithm

The algorithm realized here is the Luhn algorithm. You can do the formal proofs with some discrete math, or trust the Wikipedia Article that it is useful because:

• It detects any one digit error e.g. 1235 instead of 1234
• It detects any one transposition e.g. 1324 instead of 1234

Both errors are exceedingly common for human typists.
(Note that the ISBN10 algorithm holds some of these same properties.)

The Code

/**
A simple credit card validator that just runs the luhn algorithm against the 
given number. It doesn't even check to see if the string is long enough!
**/
class Validator
{
    /**
        Call this function with a string of digits that represent a credit card
        number.
    **/
    public static function validate(cardNumber : String) : Bool
    {
        return (luhn(cardNumber) == 0);
    }

    private static function luhn(numericString : String) : Int
    {
        var output = stringToDigitArray(numericString);
        var sum : Int = 0;
    
        var isEven : Bool = true;
        for( i in output.iterator())
        {
            if(isEven)
            {
                sum += sumOfDigits(i * 2);
            }
            else
            {
                sum += i;
            }
        
            isEven = !isEven; // Invert sign for next iteration
        }
    
        return sum % 10;
    }

    private static function stringToDigitArray(numericString : String) : Array<Int>
    {
        var output = new Array<Int>();
        for( i in 0...numericString.length)
        {
            output.push(Std.parseInt(numericString.charAt(i)));
        }
    
        return output;
    }

    private static function sumOfDigits(number : Int) : Int
    {
        var sum : Int = 0;
    
        while(number != 0)
        {
            sum += number % Std.int(10);
            number = Std.int(number / Std.int(10));
        }
    
        sum += number;
    
        return sum;
    }

    /* Examples */
    public static function main() : Void
    {
        // False
        trace(Validator.validate("1111111111111111"));
        
        // All true below this point
        trace(Validator.validate("4271058012370682"));
        trace(Validator.validate("4052047247466840"));
        trace(Validator.validate("4250112315345738"));
        trace(Validator.validate("4302220036446780"));
        trace(Validator.validate("4271382676044056"));
        trace(Validator.validate("4027883785016825"));
        trace(Validator.validate("4125875428334483"));
        trace(Validator.validate("4231380166327600"));
        trace(Validator.validate("4820020713741757"));
        trace(Validator.validate("4013112216053363"));
    }
}

HOWTO Find and Restore a Deleted SVN File/Folder

1. Change directories to your SVN project.
2. Run svn log -v > all_history.txt
3. Open all_history.txt and find the file you want (Ctrl + F is your friend!)
4. Make sure the line of the file you want begins with a D, this means it was deleted.
5. Look up above that file for the revision number, subtract one from it.
6. Run a new checkout for the version right beforehand i.e.: svn co http://hostname/path/to/files_parent_directory@revision#_right_before

Example

We want to find DataFeedList.java, here is the svn log:

------------------------------------------------------------------------
r24843 | joslewis | 2013-04-14 10:24:28 -0600 (Sun, 14 Apr 2013) | 1 line
Changed paths:
   D /trunk/software/src/bmod/gui/widgets/DataFeedList.java
   D /trunk/software/src/bmod/gui/widgets/FilterableComponentList.java
   D /trunk/software/src/bmod/gui/widgets/JValidatingTextField.java
   D /trunk/software/src/bmod/gui/widgets/WebButton.java
   D /trunk/software/src/bmod/gui/widgets/WebMenuItem.java
   M /trunk/software/src/bmod/plugin/generic/gui/ReportBugMenuItem.java

Modified ReportBugMenuItem to now work without WebButton. -~400 lines.
------------------------------------------------------------------------

We can see it was deleted (D) during revision r24843 by me on 2013-04-14 10:24:28 -0600. That means we want to actually get the version right before it was deleted, so we'll check out version 24842.

It was in the folder: /trunk/software/src/bmod/gui/widgets/, so we'll craft a new checkout with the information to get it back:

svn co http://svn.host.com/trunk/software/src/bmod/gui/widgets@24842

Run this in another folder so you don't overwrite the existing source, and you'll find the deleted item in it!

The Haxe Programming Language

This is a language that has seemed to slip by under the radar for the most part. Haxe, commonly pronounced "hex" or "hacks" is a language that targets many virtual machines, instead of the more common virtual machine that targets many languages.
It has a reasonable standard library that feels designed, much like Python's. The syntax is Go like, with identifiers following names:

class WebFetch 
{
    static function main()
    {
        var output = haxe.Http.requestUrl("http://www.google.com/");
        Sys.print(output);
    }
}

When built, this program is a ~68Kb JAR file when targeting Java or a 550Kb ELF when generating C++.
Compilation is straightforward, consisting of an internal build system that resolves libraries well, and a global repository that you can pull new packages from.
One of the biggest benefits of this language is its ability to compile and run on so many platforms; it easily handles:

• Android
• Flash
• Linux
• Mac
• Windows
• HTML + JS
• PHP
• Java (in Beta)

Example Uses

• You're a web-developer and have some business code that needs to target language of the day. Haxe can compile to language of the day without the need to translate.
• You want to code a cross-platform game to reach as broad of an audience as possible without re-writing lots of code.
• You want to develop a client for an API you publish so developers will actually use it without learning all of the languages it is going to be used in or maintaining the libraries.
• You want to develop an app that is future proof, but don't mind it being a little ugly.

Pitfalls

• There is no standardized UI system.
• The coding conventions are a strange to begin with.
• There are some obvious deficiencies in the standard library (no string compare)
• Code is slightly larger than it would be natively.

Conclusion

Overall, Haxe is a good language that I see myself using in the long run because it is so future-proof and well designed. Plus, the ability to do things easily cannot be underestimated. The example above would have taken over 100 lines of Java and about the same in C++, instead it took eight and thirty seconds to put together after knowing the language less than twenty-four hours.

Finding Strings in Raw Data

Occasionally, you'll find yourself wishing you could pull out human-readable strings from binary formats, like JPEGs, EXEs or even raw disk dumps. This may be for a variety of reasons, such as:

• Performing malware analysis
• Finding lost files
• Efficient searching

Algorithm

Actually extracting interesting text from a file is somewhat difficult because,

• you don't know what format the file is in
• you don't know what language the text is in
• you don't know how relevant a snippet is

Therefore, we can only rely on if a character is printable or non-printable, whatever that means. Then we can use information to try and weed out the junk without compromising things like IP addresses, which may look very much like junk, but are not.

The method I found that works relatively well is this:

1. Look for runs of printable characters in a file with length greater than 5
2. Look for runs of uppercase letters, lowercase letters, or numbers.
3. For each character of each run, set the value of the nth letter to n.
4. Sum the run totals
5. Sort the scores and return.

This algorithm is implemented in the code below.

Outputs

The software below strips special terminal characters (like newlines and carriage returns), and prints out items in the following format:

<score><tab><file><tab><string><newline>

Example:

00000250    dd.img  &'()*56789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz
00000176    dd.img  .IEC 61966-2.1 Default RGB colour space - sRGB
00000176    dd.img  .IEC 61966-2.1 Default RGB colour space - sRGB
00000138    dd.img  ;CREATOR: gd-jpeg v1.0 (using IJG JPEG v62), quality = 95 
00000136    dd.img  ,Reference Viewing Condition in IEC61966-2.1
00000136    dd.img  ,Reference Viewing Condition in IEC61966-2.1
00000099    dd.img  Copyright (c) 1998 Hewlett-Packard Company
00000078    dd.img  <?xpacket begin='
00000075    dd.img  Hhttp://ns.adobe.com/xap/1.0/
00000075    dd.img  Adobe Photoshop CS2 Macintosh
00000063    dd.img  $54545,,4,44455,554,,4,,,4,55456,,,,,,/5554-,,4,24,
00000058    dd.img  IEC http://www.iec.ch
00000058    dd.img  IEC http://www.iec.ch
00000051    dd.img  bottomOutsetlong
00000046    dd.img  rightOutsetlong

It appears this unallocated space actually has files!

Operation

Save the below code to reader.py and provide it paths to the files you want it to read. There are no parameters.

Source

#!/usr/bin/env python
'''
A program that extracts strings from binary files.

Usage: reader.py file [file ...]

Copyright (c) 2013, Joseph Lewis III <joseph@josephlewis.net> | <joehms22@gmail.com>
All rights reserved.

Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:

    Redistributions of source code must retain the above copyright notice, this 
    list of conditions and the following disclaimer.
    
    Redistributions in binary form must reproduce the above copyright notice, 
    this list of conditions and the following disclaimer in the documentation 
    and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

'''

import sys

ALPHABET_UPPER = frozenset("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
ALPHABET = frozenset("abcdefghijklmnopqrstuvwxyz,-. \t\n")
NUMBERS = frozenset("0123456789")
OTHER_CHARACTERS = frozenset("!\"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~ \t\n\r")
PRINTABLE = frozenset('0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~ \t\n\r')
READ_BLOCK_SIZE_B = 2048

def type_of_char(c):
    if c in ALPHABET_UPPER:
        return 'A'
    if c in ALPHABET:
        return 'a'
    if c in NUMBERS:
        return 'n'
    return 'o'

def value_of_string(string):
    ''' A heuristic to give an approximate value to a string. '''

    # make sure the string isn't total junk
    if all([c in OTHER_CHARACTERS for c in string]):
        return 0

    types = [type_of_char(c) for c in string]
    runs = [0 for c in string]

    # higher runs are better
    for i in range(1, len(types)):
        if types[i] == 'o':
            runs[i] = 0
        elif types[i] == types[i - 1]:
            runs[i] = runs[i - 1] + 1
        else:
            runs[i] = 0

    return sum(runs)

def process_string(string, extracts):
    if len(string) < 5:
        return

    score = value_of_string(string)

    if score > 0:
        extracts.append((score, path, string))

def extract_strings(path, extracts):
    '''Extracts "interesting" strings from a file'''

    mystr = []

    with open(path, 'rb') as fd:
        chars = fd.read(READ_BLOCK_SIZE_B)

        while chars != "":
            for char in chars:
                if char in "\r\n":
                    mystr.append(" ")
                elif char in PRINTABLE:
                    mystr.append(char)
                elif len(mystr) == 0:
                    continue
                else:
                    process_string("".join(mystr), extracts)
                    mystr = []
            chars = fd.read(READ_BLOCK_SIZE_B)

    process_string("".join(mystr), extracts)


if __name__ == "__main__":
    if len(sys.argv) == 1:
        print("Usage: {} file [file ...]".format(sys.argv[0]))
        exit(1)

    # a list of tuples (score, document, string)
    extracts = []

    for path in sys.argv[1:]:
        extract_strings(path, extracts)

    extracts = sorted(extracts, reverse=True)
    for score, path, string in extracts:
        print("{:08.0f}\t{}\t{}".format(score, path, string))

Friday Operating System News

Operating Systems

NixOS is a neat little OS that is built around a single config file. The file can be moved to a different computer, and it'll set itself up as a clone, or as you're more likely to use it, as a single file that does version control on your system (so next time you upgrade, you can roll it back right away!)

Jolla has released it's first phones running Sailfish OS.

Finding Deleted JPEGs in Disk Dumps

If you've ever accidentally deleted items from your digital camera, or want to find them from a drive that has been lost, this script could be for you!

It works by looking through a disk image for a sequence of bytes that signify the beginning and end of a JPEG image.

Running It

First save the below script as ImageCarver.java

Then compile it:

javac ImageCarver.java

Afterwards, run it with the path to the disk image you want it to search:

java ImageCarver disk.img

It will report images it found, as well as the locations in the disk that it found them:

1.jpg 0xe3fa 0x10272
2.jpg 0xe000 0x20865
3.jpg 0x1000 0x2557e
4.jpg 0x41000 0x4437d
5.jpg 0x26000 0x654d4
6.jpg 0x25000 0x96816
7.jpg 0x86000 0x9eca0
8.jpg 0x6d000 0xdc614
9.jpg 0xe2000 0xe7ac9
10.jpg 0xa4000 0xeb28a
11.jpg 0xed000 0xfc9a9
12.jpg 0x136000 0x13b08e
13.jpg 0x1b5144 0x1b629e
14.jpg 0x1b5000 0x1b794a
15.jpg 0x1b67f0 0x1bea75
16.jpg 0x1c9000 0x1cfada
17.jpg 0x22d000 0x237824
18.jpg 0x281000 0x288928

The Script

import java.io.IOException;
import java.io.OutputStream;
import java.nio.ByteBuffer;
import java.nio.channels.SeekableByteChannel;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;
import java.util.LinkedList;

/**
 * Carves images from a file given from the command line.
 * 
 * @author Joseph Lewis <joehms22@gmail.com>
 *
 */
public class ImageCarver 
{
    byte[] STARTING_BYTES = new byte[]{(byte)0xFF, (byte)0xD8,(byte)0xFF};
    byte[] ENDING_BYTES = new byte[]{(byte)0xFF,(byte)0xD9};
    int imgno = 0;


    /**
     * Carves images out of a file.
     * @param sbc - the byte channel to read from.
     * @throws IOException - on a file error
     */
    public ImageCarver(SeekableByteChannel sbc) throws IOException
    {
        // find all potential starting and ending points in the file.
        LinkedList<Long> startingPoints = ringMatch(sbc, STARTING_BYTES);
        LinkedList<Long> endingPoints = ringMatch(sbc, ENDING_BYTES);

        // keep writing out we're out of images
        while(startingPoints.size() > 0)
        {
            carveImage(sbc, startingPoints, endingPoints);
        }
    }

    /**
     * Carves an image out of the file.
     * @param sbc - the channel to read from
     * @param starts - the start positions of the image
     * @param ends - the end positions of the image
     * @throws IOException - on error
     */
    public void carveImage(SeekableByteChannel sbc, LinkedList<Long> starts, LinkedList<Long> ends) throws IOException
    {
        // clear off no longer useful end points
        while(starts.peek() > ends.peek())
        {
            ends.pop();
        }
    
        // If ends is empty, add the literal file end.
        if(ends.size() == 0)
        {
            ends.push(sbc.size());
        }
    
        // get our starting position.
        long sp = starts.pop();
    
        // Check to see if there's an image inside of us.
        if(starts.size() > 0 && starts.peek() < ends.peek())
        {
            carveImage(sbc, starts, ends);
        }
    
        // get our closest end point.
        long endloc = ends.pop();
    
        imgno++;
        createImage(imgno + ".jpg", sbc, sp, endloc);
    }

    /**
     * Extracts an image from the SeekableByteChannel.
     * @param name - the image name
     * @param src - the channel to read from
     * @param begin - the offset to the beginning of the image
     * @param end - the offset to the end of the image
     * @throws IOException - on error
     */
    public void createImage(String name, SeekableByteChannel src, long begin, long end) throws IOException
    {
        // alert the user about the image we're outputting
        System.out.println(String.format("%s 0x%x 0x%x", name, begin, end));
    
        // write out the given slice of bytes
        try(OutputStream os = Files.newOutputStream(Paths.get(name), StandardOpenOption.CREATE))
        {
            src.position(begin);
            ByteBuffer b = ByteBuffer.allocate((int) (end - begin));
            src.read(b);
            os.write(b.array());
        }
    }

    /**
     * Searches through a channel looking for a given array of bytes to match.
     * 
     * @param sbc - the channel to read from
     * @param toMatch - the bytes to match in the stream
     * @return a list of all offsets where the given bytes are found
     * @throws IOException - on file read error
     */
    public LinkedList<Long> ringMatch(SeekableByteChannel sbc, byte[] toMatch) throws IOException
    {
        // holds all found vars
        LinkedList<Long> finds = new LinkedList<Long>();
    
        for(long i = 0; i < sbc.size() - toMatch.length; i++)
        {
            ByteBuffer b = ByteBuffer.allocate(toMatch.length);
            sbc.position(i);
            sbc.read(b);
        
            boolean matches = true;
            for(int j = 0; j < toMatch.length; j++)
            {
                if(b.array()[j] != toMatch[j])
                {
                    matches = false;
                    break;
                }
            }
        
            if(matches)
            {
                finds.add(i);
            }
        
        }
        return finds;
    }

    public static void main(String[] args) throws Exception 
    {
        // Make sure we have an arg.
        if(args.length != 1)
        {
            System.out.println("Must supply exactly one argument.");
            return;
        }
    
        Path p = Paths.get(args[0]);
    
        try (SeekableByteChannel sbc = Files.newByteChannel(p)) 
        {
            new ImageCarver(sbc);
        }
        catch (IOException x) 
        {
            System.out.println("Caught exception: " + x);
        }
    }
}