Credit Card Number Detection Algorithm (Luhn Algorithm)

I would like to share with you an algorithm that I came across by chance at work. It is used to detect valid credit card numbers. Apparently credit card numbers are not generated randomly but they follow an algorithm and these numbers can be detected with an algorithm developed by Hans Peter Luhn at IBM in 1950s.

This algorithm is known also as "modulus 10" or "mod 10" algorithm. It is pretty simple and is widely used to conceal credit card numbers for security reasons. We always see in online shopping e-commerce sites that our credit card number is displayed back to us with only the last 4 digits visible and the rest is masked with an asterisk *. This is done with the help of this algorithm.

How it works?

1. From the right-most number moving to the left, double the value of every second number. (Right-most digit is called the check digit)
1. If the result of this doubling operation is greater than 9, sum the digits of the result.
2. Sum all the digits.
3. If the total modulus 10 is 0, then it is a valid credit card number.

Let's take an example credit card number that is valid and see the calculation steps: 2012444444444444

CC number	2	0	1	2	4	4	4	4	4	4	4	4	4	4	4	4
Double every second digit	4	0	2	2	8	4	8	4	8	4	8	4	8	4	8	4
Sum of digits	4	0	2	2	8	4	8	4	8	4	8	4	8	4	8	4	=80

Let's take another number that is not a valid example: 1010666666666666

CC number	1	0	1	0	6	6	6	6	6	6	6	6	6	6	6	6
Double every second digit	2	0	2	0	12	6	12	6	12	6	12	6	12	6	12	6
Sum of digits	2	0	2	0	3	6	3	6	3	6	3	6	3	6	3	6	=58

How to swap two integer values without a temp variable?

This question has been asked to me for many times by my algorithm teachers. I just wanted to write about it to help new algorithm students to find the answer to their homeworks :)

Let a and b be two integer variables. To swap the values of these variables, some arithmetic operations as follows must be applied.

a = a - b;
b = b + a;
a = b - a;

Lets continue with a numerical example where
a = 3 and b = 5


a = 3 - 5 = -2;
b = 5 + (-2) = 3;
a = 3 - (-2) = 5;


As a result of these operations, the values are swapped without using any additional temporary variable. Now you can write down the answer to your homework :)

Steganalysis: Chi-Square Attack & LSB Enhancement

I have developed a small Java program to perform Chi-Square attack and LSB Enhancement attack on 24-bit BMP images.

What does LSB Enhancement mean?
Well, it is the process of manipulating the least-significant-bit(LSB) of image data in order to produce an output to discover the embedded data.

How it works?
First of all we need to read the image data in Java. I used an already implemented Java class which was based on the code from authors Abdul Bezrati and Pepijn Van Eeckhoudt. The class is called BitmapLoader and it can read both 8-bit and 24-bit BMP images. The method loadBitmap(String file) returns a BufferedImage of type BufferedImage.TYPE_4BYTE_ABGR which means that when a pixel value is read using image.getRGB(x, y) it will return a 32-bit integer value of which the left most 8 bits will represent the ALPHA component, next 8 bits BLUE component, next 8 bits GREEN component and the least significant 8 bits will represent the RED component of the pixel. We can read these components individually by performing bitwise shift operations on the RGB value as 

int pRGB = image.getRGB(x, y);

int alpha = (pRGB >> 24) & 0xFF;

int blue = (pRGB >> 16) & 0xFF;

int green = (pRGB >> 8) & 0xFF;

int red = pRGB & 0xFF;

LSB enhancement means setting the component value to 255 if the least-significant-bit is 1 or leave as it is if 0. As a result of this operation, the image will have some flashy colours in the parts where the LSBs were 1s.

How it works in java? First we need to set the alpha component to 255 or the background of the image will be transparent. Then we need to check the red, green and blue components if the LSBs are 1, if they are, we will set these values to 255. It is performed with the following lines of code in Java:

int pRGB = 255 << 24; //set the alpha component

int temp = 0;

if ((red & 0x01) == 1) {//check if the LSB is 1

    pRGB += 255;

}

if ((green & 0x01) == 1) {//check if the LSB is 1

    temp = pRGB;

    pRGB = 255 << 8;

    pRGB += temp;

}

if ((blue & 0x01) == 1) {//check if the LSB is 1

    temp = pRGB;

    pRGB = 255 << 16;

    pRGB += temp;

}

lsbImage.setRGB(x, y, pRGB);//set the RGB value of the image.

When the above operation is performed on all pixels of the image, the resulting lsbImage which is of type BufferedImage will reveal the parts of the image with the hidden data.

---

How Chi-Square attack works?

This attack was developed by Andreas Westfeld and Andreas Pfitzmann in 2000 (Andreas Westfeld and Andreas Pfitzmann, Attacks on Steganographic Systems. Breaking the Steganographic Utilities EzStego, Jsteg,Steganos, and S-Toolsand Some Lessons Learned, 2000).

First of all, we need to know what is Chi-Square analysis? It is a statistical test to measure if a given set of observed data and an expected set of data are similar or not. This is the main idea, you can read about it in more details in any statistics book.

The idea of this attack is to compare Pair-of-Values' observed frequencies with their expected frequencies and calculate p value which will represent the probability of having some embedded data in an image.

What do we mean by Pair-of-Values? According to Westfeld & Pfitzmann, when some data like encrypted text is embedded into an image the LSB values of the original data change in a way that the number of these pairs become nearly equal while they differ so much when there is no embedding. We can see pairs of values as the following bit sequences in our case where we have 8-bit components. As a result we have 128 pairs of values like 0-1, 2-3, 4-5, ..., 254-255. What we do with these values? We will count the occurrences of the individual colour values in the image and we will come up with the observed frequencies data set which will be used in the chi-square test. But we also need an expected data set which is explained by Westfeld & Pfitzmann as the average of the occurrences of the values in a pair.

00000000

00000001

00000010

00000011

00000100

00000101

........

11111110

11111111

For the observed data set we just need to take the frequency of one of the pairs. It will not make any difference because the expected value is the average of both values in a pair which means that both of the values are in the same distance to the average. For example, we counted 800 occurrences for value 0 and 200 occurrences for value 1. The expected value will be the average of these two values which will result in 500. Both of the observed values are at the same distance to the average which is 300. 

---

How is it implemented in Java?
I have a class named PoV which has only the following attribute

private long[] pov = new long[256];

and three methods as

public double[] getExpected() {

        double[] result = new double[pov.length / 2];
        for (int i = 0; i < result.length; i++) {
            double avg = (pov[2 * i] + pov[2 * i + 1]) / 2;
            result[i] = avg;
        }
        return result;
}
public void incPov(int i) {
        pov[i]++;
}
public long[] getPov() {
        long[] result = new long[pov.length / 2];
        for (int i = 0; i < result.length; i++) {
            result[i] = pov[2 * i + 1];
        }
        return result;

---

How do we perform the Chi-square test on the image?
The performed test is the iterated version of the above described attack and it is performed after reading a predefined amount of data(chunk size) is read. I chose chunk-size as 128 bytes which means after reading 128 bytes of image data, a test is performed and its result is stored. The total number of tests/chunks in the image is
numOfChunks=(int)(Math.floor((width*height*3)/chunkSize)+1);
which will also be the width in pixels of the output generated at the end. Sample outputs of the program are given below.

480x360 embedded with 6 KB data

LSB Enhancement output

Chi-square attack output

Download available at: https://sourceforge.net/projects/chi-square/

FFMPEG COMPILATION IN WINDOWS USING MINGW32/MSYS

FFMPEG COMPILATION IN WINDOWS USING MINGW32/MSYS

1-)Minimal SYStem (MSYS) installation
Download the MSYS executable from here and install into c:\msys. Do not continue with the postinstall operation.
2-)Update MSYS
Update the MSYS to a more recent version (1.0.11) by downloading the package from here and copy mount.exe, msys-1.0.dll and ps.exe into c:\msys\bin directory.
3-)MSYS DTK(Developer Tool Kit)
Download the DTK from here and install into c:\msys.
4-)Update BASH
Download bash version 3.1 from here and copy bash.exe and sh.exe from the bin subdirectory to c:\msys\bin directory and replace sh.exe with the old one.
5-)Install MINGW
Download MINGW 5.1.4 from here and follow the instructions as follows:
-Download only
-Candidate
-Check the followings
MinGW base tools (autoselected)
g++ compiler
and run the exe again but this time follow the instructions as follows
-Download and install
-Candidate
-Check the followings
MinGW base tools (autoselected)
g++ compiler
make the installation folder as c:\msys\mingw it will download the following packages
mingw-runtime-3.10.tar.gz
w32api-3.7.tar.gz
binutils-2.16.91-20060119-1.tar.gz
gcc-core-3.4.5-20060117-1.tar.gz
gcc-g++-3.4.5-20060117-1.tar.gz
6-)Configuring FSTAB
Rename the file in c:\msys\etc\fstab.sample as fstab and replace the the line c:/mingw to c:/msys/mingw using a text editor like Notepad++. Notepad++ is recommended as the text editor for all of the editing operations. It can be downloaded from here Note:Open c:\msys\msys.bat with Notepad++ and replace “-fn Courier-12” to “-fn Courier-16” to make the fonts larger in the msys window.
7-)Update MAKE
Download the MAKE MSYS v 3.81 from here and copy the files in the bin and share folder into the same folders under
c:\msys\mingw\bin and c:\msys\mingw\share.
8-)Coreutils
Download the coreutils package from here and copy the whomai.exe to c:\msys\minw\bin
9-)MINGW Utils
Downlaod the package from here and copy the unix2dos.exe to c:\msys\mingw\bin.
10-)Update GCC 3.4.5 to 4.3.3
Download the package from here and copy all of the directories to c:\msys\mingw\<correponding directory>
11-)Update GCC Core 3.4.5 to 4.3.3
Download the package from here and copy all of the directories to c:\msys\mingw\<correponding directory>
12-)ICONV
Download the package from here and install it into c:\msys\mingw.
13-)MINGW RUNTIME Update From 3.10 to 3.15.2
Download the package from here and copy all of the directories to c:\msys\mingw\<correponding directory>
14-)W32 API Update from 3.7 to 3.13
Download the package from here and copy all of the directories to c:\msys\mingw\<correponding directory>
15-)BINUTILS Update from 2.16.91 to 2.19.1
Download the package from here and copy all of the directories
to c:\msys\mingw\<correponding directory>

AFTER ALL OF THESE OPERATIONS ITS TIME TO GET FFMPEG FROM SVN

In order to get ffmpeg from svn, first we have to download and install a SVN client, TortoiseSVN is recommended. TortoiseSVN can be downloaded from http://tortoisesvn.tigris.org/.
After installing SVN client we can download the ffmpeg SVN by performing a checkout to the address svn://svn.mplayerhq.hu/ffmpeg/trunk

COMPILING FFMPEG WITHOUT ADDITIONAL LIBRARIES

After installing MSYS and MINGW there will be a shortcut on your desktop with a blue M icon. Just double click on it to run MSYS or run C:\msys\msys.bat Assuming that the ffmpeg is downloaded to c:\ffmpeg just type
cd c:\ffmpeg
./configure --enable-memalign-hack --extra-cflags=-fno-common --enable-static --disable-shared
If an error occurs like “pr: Command not found” copy the pr.exe file in the bin directory of coreutils-5.97-MSYS-1.0.11-snapshot.tar.bz2 that you previously downloaded to c:\msys\bin.
make
After the make operation, if you see “strip ffmpeg.exe” as the last line of the terminal, it means that the compilation is successful and its turn for the next command:
make install
COMPILING FFMPEG WITH ADDITIONAL STATIC LIBRARIES

For all of the configure commands we will use the following instruction
./configure --prefix=/mingw --enable-static --disable-shared
make
make install
1-)ZLIB-1.2.3
Download the package from here and extract the package to c:\msys\zlib-1.2.3 and follow the instructions:
cd c:\msys\zlib-1.2.3
./configure --prefix=/mingw --enable-static –disable-shared
make
make install
Delete the zlib-1.2.3 directory after installation.

2-)XVIDCORE-1.2.1
Download the package from here and
extract the package to c:\msys\xvidcore-1.2.1 and follow the instructions:
cd c:\msys\xvidcore-1.2.1
./configure --prefix=/mingw --enable-static –disable-shared
make
make install
Delete the xvidcore-1.2.1 directory after installation.

3-)SPEEX-1.2rc1
Download the package from here and extract the package to c:\msys\speex-1.2rc1 and follow the instructions:
cd c:\msys\speex-1.2rc1
./configure --prefix=/mingw --enable-static –disable-shared
make
make install
Delete the speex-1.2rc1 directory after installation.

4-)LIBOGG-1.1.3
Download the package from http://www.xiph.org/downloads/ and extract the package to
c:\msys\libogg-1.1.3 and follow the instructions:
cd c:\msys\libogg-1.1.3
./configure --prefix=/mingw --enable-static –disable-shared
make
make install
Delete the libogg-1.1.3 directory after installation.

5-)LIBOIL-0.3.16
Dwonload the package from here and extract the package to c:\msys\liboil-0.3.16 and follow the instructions:
cd c:\msys\liboil-0.3.16
./configure --prefix=/mingw --enable-static –disable-shared
make
make install
Delete the liboil-0.3.16 directory after installation.

6-)GLIB-2.18.3 and PKG-CONFIG-0.23-2
Download the glib package from here and extract the files into c:\msys\mingw\<corresponding directory>
Download the package from here and extract the files into c:\msys\mingw\<corresponding directory>

7-)LIBSCHROEDINGER-1.0.7
Download the package from here and extract the package into c:\msys\schroedinger-1.0.7and follow the instructions:
cd c:\msys\schroedinger-1.0.7
./configure --prefix=/mingw --enable-static –disable-shared
make
make install
Delete the schroedinger-1.0.7 directory after installation.

8-)LIBTHEORA-1.0
Download the package from http://www.theora.org/downloads/ and extract the package into c:\msys\libtheora-1.0 and follow the instructions:
cd c:\msys\libtheora-1.0
./configure --prefix=/mingw --enable-static –disable-shared
make
make install
Delete the libtheora-1.0 directory after installation.

9-)LIBMP3LAME
Download the package from here and extract to c:\msys\lame-398 and follow the instructions:
cd c:\msys\lame-398
./configure --prefix=/mingw --enable-static –disable-shared
make
make install
Delete the lame-398 directory after installation.

10-)AMRNB-7.0.0.2
Download the package from here and extract th epackage to c:\msys\amrnb-7.0.0.2 and follow the instructions:
cd c:\msys\amrnb-7.0.0.2
./configure --prefix=/mingw --enable-static –disable-shared
make
make install
Delete the amrnb-7.0.0.2 directory after installation.

11-)AMRWB-7.0.0.3
Download the package from here and extract the package into c:\msys\amrwb-7.0.0.3 and follow the instructions:
cd c:\msys\amrwb-7.0.0.3
./configure --prefix=/mingw --enable-static –disable-shared
make
make install
Delete the amrwb-7.0.0.3 directory after installation.

12-)FAAD-2.6.1
Download the packge from here and extract the package into c:\msys\faad-2.6.1 and follow the instructions:
cd c:\msys\faad-2.6.1
./configure --prefix=/mingw --enable-static –disable-shared
make
make install
Delete the faad-2.6.1 directory after installation.

13-)FAAC-1.26
Download the package from here and extract the package into c:\msys\faac-1.26 and follow the instructions:
cd c:\msys\faac-1.26
./configure --prefix=/mingw --enable-static –disable-shared
make
make install
Delete the faac-1.26 directory after installation.

14-)BZIP2
Download the package from here and extract the package into c:\msys\bzip2-1.0.5 and download the patch from here and save into c:\msys\bzip2-1.0.5 and follow the instructions:
cd c:\msys\bzip2-1.0.5
patch -p0 < bzip2-1.0.5-extensions.diff
make
make install PREFIX=/mingw
Delete the bzip2-1.0.5 directory after installation.

15-)LIBGSM-1.0.12
Download the package from here and extract the cabinet file components to the corresponding directories in c:\msys\mingw\

16-)LIBVORBIS-1.2.2
Download the package from http://www.xiph.org/downloads/ and extract the package into c:\msys\libvorbis-1.2.2 and follow the instructions:
cd c:\msys\libvorbis-1.2.2
./configure --prefix=/mingw --enable-static –disable-shared
make
make install
Delete the libvorbis-1.2.2 directory after installation.

17-)NASM-2.06rc1(May be needed before installing one of the previous libraries-libmp3lame-)

Download the package from here and extract the package to c:\msys\nasm-2.06rc1 and follow the instructions:
cd c:\msys\nasm-2.06rc1
./configure --prefix=/mingw --enable-static –disable-shared
make
make install
Delete the nasm-2.06rc1 directory after installation.

PROBLEMS THAT CAN OCCUR WHILE COMPILATION/INSTALLATION

Note: The order of installation of the above libraries may be different but its most likely as above. If any other library or component is needed while installation of a library, just apply the required step there. The order may be different because it took me 3 days to compile and apply the configuration above :)

1-)Assembler Needed-If an error occurs like nasm or yasm is needed or not found, just apply the step #17 explained above.
2-)Error pr:Command not found- This can occur while configuration.Copy the pr.exe file in the bin directory of coreutils-5.97-MSYS-1.0.11-snapshot.tar.bz2 that you previously downloaded to c:\msys\bin.
3-)Schroedinger Not Found: This can poccur while configuration. Apply the steps 4-5-6-7 under

COMPILING FFMPEG WITH ADDITIONAL STATIC LIBRARIES in exact order.

ATTACHING FFMPEG TO FOBS_JMFSTUDIO MEDIA PLAYER

1-)Download FOBS
Download FOBS-0.4.2 from here both the source code and the binaries.

2-)Install Python
Download Python2.6.2 from http://www.python.org/ and install into c:\Python.

3-)Download SCONS
Download SCONS-local-1.2.0.d20090223 from http://www.scons.org/

4-)Unpacking
Unpack the FOBS under c:\msys\fobs.
Unpack SCONS-local-1.2.0.d20090223 into the c:\msys\fobs\scons-local\.
Unpack the FOBS\fobs-0.4.2\resources\current-ffmpeg.tar.bz2 into c:\msys\fobs\ffmpeg .

5-)FFMPEG Recompilation
-Run MSYS and follow the instructions:
$ cd /fobs/ffmpeg
$ ./configure --enable-memalign-hack --extra-cflags=-fno-common --enable-static --disable-shared
--disable-debug --enable-gpl --enable-nonfree --enable-avfilter --enable-avfilter-lavf --enable-avisynth
--enable-postproc --enable-libamr-nb --enable-libamr-wb --enable-libgsm --enable-libfaac --enablelibfaad
--enable-libmp3lame --enable-libschroedinger --enable-libtheora --enable-libvorbis --enablelibxvid
–prefix=/fobs/external
$ make
$ make install
$ cp libavformat/avi.h /fobs/external/include/libavformat/
$ cp libavformat/riff.h /fobs/external/include/libavformat/
$ mkdir /fobs/external/include/libswscale
$ cp libswscale/swscale.h /fobs/external/include/libswscale/swscale.h

6-)Environment Variables
Check whether the environment variables of Python and Java are existent in your system path. If not : Go to
MyComputer->Properties->Advanced->Environment Variables->System Variables->PATH and append the paths where your python and java JDK bin directory is. Mine is C:\Python; and C:\Program Files\Java\jdk1.6.0_13\bin;
RESTART THE COMPUTER AFTER APPLYING THE CHANGES

7-)Build Script
$ cd /fobs
$ ./buildFobs.sh FFMPEG_HOME=/fobs/external FOBS4JMF=yes

After the project has been built, the "fobs/dist" directory will contain the following:
dist/include, dist/lib : Static library with C++ API classes and header files needed to use Fobs in your C++ project dist/jmf/ : Dynamic library with JMF plugin and Jar with Java part of the implementation. dist/test/ : Some example applications to get help learning the Fobs API.
If you want to use the ffmpeg you've build with Fobs_jmstudio just copy
/fobs/jmf/fobs4jmf.dll,/fobs/jmf/fobs4jmf.jar,/fobs/jmf/jmf.jar and /fobs/jmf/jmf.properties into the folder where Fobs_jmstudio exists in the downloaded Fobs binaries folder and the media player is ready to use.

ERRORS THAT CAN OCCUR WHILE BUILDING FOBS

Value Error: too many values to unpack:
File “C:\msys\fobs\SConstruct”, line 29: …
Solution : Go to c:\msys\fobs\external\lib\pkgconfig and delete the entry “-Lc:\msys\fobs\external\lib” from the line Libs: -L${libdir} int the files libavcodec.pc,libacdevice.pc,libavfilter.pc and libavformat.pc
Errors in Decoder.cpp , Encoder.cpp and Transcoder.cpp
Note : Do these steps if errors including 'strcpy','memcpy','memset','abs','INT_MAX', etc occur.
Decoder.cpp -> Just add the following lines into the file where the #include lines are:
#include <string.h>
#include <cmath>
Change the following lines
if(isVideoPresent()) res = ::abs(t2-t1) <= 1000.0/getFrameRate();
else res = ::abs(t2-t1) <= 1000.0/getAudioSampleRate();
with
if(isVideoPresent()) res = ::abs((float)(t2-t1)) <= 1000.0/getFrameRate();
else res = ::abs((float)(t2-t1)) <= 1000.0/getAudioSampleRate();

Encoder.cpp ->Just add the following lines into the file where the #include lines are:
#include <string.h>
#include <limits.h>

Transcoder.cpp->Just add the following lines into the file where the #include lines are:
#include <string.h>
#include <stdlib.h>

Redefinition Errors->videohdr_tag,CAPTUREPARMS,WM_CAP_SET_CALLBACK_VIDEOSTREAM,WM_CAP_DRIVER_CONNECT,
WM_CAP_DRIVER_DISCONNECT ,WM_CAP_GET_VIDEOFORMAT, WM_CAP_SET_VIDEOFORMAT, WM_CAP_SET_PREVIEW, WM_CAP_SET_OVERLAY,WM_CAP_SEQUENCE_NOFILE,WM_CAP_SET_SEQUENCE_SETUP,WM_CAP_GET_SEQUENCE_SETUP,...
Solution->Open the file c:\msys\fobs\ffmpeg\libavdevice\vfwcap.c and make the followinf lines as comment lines.

//#define WM_CAP_SET_CALLBACK_VIDEOSTREAM (WM_CAP_START + 6)
//#define WM_CAP_DRIVER_CONNECT (WM_CAP_START + 10)
//#define WM_CAP_DRIVER_DISCONNECT (WM_CAP_START + 11)
//#define WM_CAP_GET_VIDEOFORMAT (WM_CAP_START + 44)
//#define WM_CAP_SET_VIDEOFORMAT (WM_CAP_START + 45)
//#define WM_CAP_SET_PREVIEW (WM_CAP_START + 50)
//#define WM_CAP_SET_OVERLAY (WM_CAP_START + 51)
//#define WM_CAP_SEQUENCE_NOFILE (WM_CAP_START + 63)
//#define WM_CAP_SET_SEQUENCE_SETUP (WM_CAP_START + 64)
//#define WM_CAP_GET_SEQUENCE_SETUP (WM_CAP_START + 65)
// typedef struct videohdr_tag {
// LPBYTE lpData;
// DWORD dwBufferLength;
// DWORD dwBytesUsed;
// DWORD dwTimeCaptured;
// DWORD dwUser;
// DWORD dwFlags;
// DWORD_PTR dwReserved[4];
// } VIDEOHDR, NEAR *PVIDEOHDR, FAR * LPVIDEOHDR;

// typedef struct {
// DWORD dwRequestMicroSecPerFrame;
// BOOL fMakeUserHitOKToCapture;
// UINT wPercentDropForError;
// BOOL fYield;
// DWORD dwIndexSize;
// UINT wChunkGranularity;
// BOOL fUsingDOSMemory;
// UINT wNumVideoRequested;
// BOOL fCaptureAudio;
// UINT wNumAudioRequested;
// UINT vKeyAbort;
// BOOL fAbortLeftMouse;
// BOOL fAbortRightMouse;
// BOOL fLimitEnabled;
// UINT wTimeLimit;
// BOOL fMCIControl;
// BOOL fStepMCIDevice;
// DWORD dwMCIStartTime;
// DWORD dwMCIStopTime;
// BOOL fStepCaptureAt2x;
// UINT wStepCaptureAverageFrames;
// DWORD dwAudioBufferSize;
// BOOL fDisableWriteCache;
// UINT AVStreamMaster;
// } CAPTUREPARMS;