Steganography

img01

Steganographic storage of encrypted files in images.

What I find truly fascinating is that there is no way to tell if an image contains steganographically hidden encrypted data. Even if you know every line of the source code of the program that you suspect may have been used to hide the data, you still have nothing to help you prove anything.
If the least significant bits in the RGB-values contains encrypted data they should appear to be random. But the least significant bits in an ordinary image on the other hand, could be expected to be less random and show a bit more regional uniformity.

Store in pixel
But randomness in the least significant bits does not constitute proof that there are encrypted data hidden. The randomness of the RGB-values could originate from natural minute color shade variations in the surface of the physical object being photographed or be the result of an image editor filter.

I’ve been working on an encryption program in C# for a couple of days. It encrypts files and hides the encrypted data steganographically inside images.

The portrait above actually does contain data that can be extracted and be visually interpreted in an unexpected way. Hidden in the above images is another image. The image you see below:

img02

I think that maybe it’s wrong to say that the initial image contains hidden data. There are no hidden data. All data in the initial image is visually represented on the screen. The question is how you interpret the data.

To make things more interesting I can reveal that the above bluish image also contains something that you might not expect.

Encoded in the pixels is a text file with the 81 verses of the ancient Tao Te Ching by Lao Tzu.

1
The Tao that can be trodden is not the enduring and
unchanging Tao. The name that can be named is not the enduring and
unchanging name.

(Conceived of as) having no name, it is the Originator of heaven
and earth; (conceived of as) having a name, it is the Mother of all
things.

Always without desire we must be found,
If its deep mystery we would sound;
But if desire always within us be,
Its outer fringe is all that we shall see.

Under these two aspects, it is really the same; but as development
takes place, it receives the different names. Together we call them
the Mystery. Where the Mystery is the deepest is the gate of all that
is subtle and wonderful.

Above you see only the first verse. The bluish image contains all 81 verses!

 

 

 

 

Annonser

The probability of finding a string of n characters

I tried to google this today but I only found a lot of unnecessarily complicated stuff. I wanted something simple but mathematically exact so I had to figure out this myself.

 // p(n,m,b) - the probability of finding at least one occurence of a string of n characters (or digits/symbols)
 // (not starting and ending with the same character) in a larger random string of m characters
 // b - is the number of different types of characters
 double p(int n, int m, int b) { return f(n,m,b) / Math.Pow(b,m); }
 double f(int n, int m, int b) { return m<n ? 0 : b * f(n,m-1,b) + Math.Pow(b,m-n) - f(n,m-n,b); }

Compare this with the standard function for calculating an approximate probability…

double pa(int n, int m, int b) { return 1 - Math.Pow((Math.Pow(b,n)-1) / Math.Pow(b,n), m-n+1); }

The f-function above calculates the total number of possible ways that the the sought for string can appear in the larger random string. Although it’s pretty short it’s not particularly fast. I made a much faster algorithm based on this idea…

formula

For example: Let’s say you want to calculate the probability of finding a particular 5 digit number in a random sequence of 18 digits. We first use the f-function to calculate the number of possible ways it can occur:

formula.sample

The the probability is given by:

ratio

Here’s my faster algorithm

double f(int n, int m, int b)
{
    int nn = n; int sg = 1; int p = 0;
    int q = 0; int a = 1; double sum = 0;
    do {
        q = m-nn;
        p = q+a;
        sum += sg * Combin(p,q) * Math.Pow(b,q);
        sg = -sg;
        a++;
        nn += n;
    } while (m-nn >= 0);
    return sum;
}

”Combin(p,q)” is of course the combination-function – ”p over q”.

C++ suger

”Vilket programmeringsspråk är bäst?” Ofta ser man denna fråga dyka upp i olika programmeringsforum på nätet. Sen följer med stor sannolikhet en hätsk debatt utan några gråskalor. Varje debattör framhåller ofta ett enda språk som det i särklass bästa: ”Ska man programmera på riktigt så är det bara X som gäller. Allt annat är skräp”. Inte sällan ser man en tendens att betrakta krånglig lågnivåprogrammering som ”finare” är enklare högnivåprogrammering.

Själv gillar jag att tänka på olika programmeringsspråk ungefär som olika konstformer: olja, akryl, akvarell, tusch, blyerts, torrnål, etsning, keramik, glas, skulptur… Vilken konstform är bäst? Ingen konstform är naturligtvis bäst. Men sen när vi kommer till den funktionella aspekten på specifika programmeringsuppdrag så finns det givetvis viktiga faktorer att ta i beaktande. Där kan man lätt ställa upp vissa tumregler. En sådan tumregel skulle kunna vara:

Eftersom tid är pengar – välj ett språk på så hög nivå som möjligt men som ändå på ett adekvat sätt löser uppgiften.

Ibland kanske den bästa lösningen är att göra den övergripande strukturen i ett högnivåspråk och sen programmera vissa resurskritiska procedurer i nåt lågnivåspråk. Det allra bästa är förstås om man kan utnyttja att någon annan redan har gjort den tidsödande lågnivåprogrammeringen tidigare. Om nån annan reda gjort jobbet förrut – varför uppfinna hjulet en gång till?

Om man på ett smart och kostnadseffektivt sätt vill bygga ett hus – varför först sätta sig ner och i minsta detalj designa alla spikar och skruvar?

Nu ska vi jämföra tre olika språk hur de kan lösa en konkret programmeringsuppgift – att räkna ut fakulteten av en miljard.

För de som inte är så matematiskt bevandrade kan jag säga att fakulteten av ett tal x är produkten av alla hela tal från ett upp till talet x. Fakulteten av 8 är alltså 1*2*3*4*5*6*7*8. Fakulteten sticker snabbt iväg och blir ruskigt stor för större tal. Fakulteten av 63 är ett tal som är större än det beräknade antalet partiklar i universum. Min TI-83 räknare kan nätt och jämt räkna ut fakulteten av 69. Det blir ungefär 1,7112 * 10^98. Högre än så klarar den inte.

Själv har på senaste tiden kommit att bli ganska förtjust i språket C# (C sharp). Det är ett språk som ligger på en slags mellannivå och har fördelar som vanligtvis tillkommer både hög- och lågnivåspråk. Här nedan är mitt C#-program för att räkna ut fakulteten på en miljard.

 

double ax = 1;

double ay = 0;

double x;

double NumberToDivideByPower = 0;

double NumberToDivideBy = 1;

DateTime t1 = DateTime.Now;

for (double b = 2; b <= 1000000000; b++)

{

    x = b / NumberToDivideBy;

    if (x == 10)

    {

        NumberToDivideBy *= 10;

        NumberToDivideByPower++;

        x = 1;

    }

    ay += NumberToDivideByPower;

    ax *= x;

    if (ax >= 10)

    {

        ax /= 10;

        ay++;

    }

}

TimeSpan tt = DateTime.Now – t1;

MessageBox.Show(”(1*10^9)! = ” + ax.ToString() + ” * 10 ^ ” + ay.ToString()

    + ”\r\n\r\n” + ”Tidsåtgång:” + tt.ToString());

 

På min 1,2 GHz laptop tar denna beräkning c:a 48 sekunder. Jag var emellertid inte nöjd. Jag tänkte att det borde gå att göra ett snabbare program med ett annat språk. Valet föll på C++.

 

Jag gjorde alltså en C++-version av ovanstående program men programmet ser i princip identiskt ut bortsett från att jag valt att ändra vissa variabeltyper för att uppnå bättre prestanda. I slutänden visar det sig ändå att C++ och C#-programmen i princip är lika snabba. Finns det ändå en chans att göra programmet snabbare? Svaret är förstås Assembler. Assemblerversionen jobbar lite annorlunda än C#/C++-versionerna. Mycket av matematiken sker på bit-nivå.

 

 

 

TITLE BillionFactorial     (BillionFactorial.asm)

 

; This program calculates the factorial of 1 billion very fast

; with four significant hexadecimal digits

; Last update: 2008-05-17

; by Gustav Bonds

 

.code

main PROC

 

    mov     eax,1          ; mantissa of factorial

    mov     ebx,1          ; counter from 1 to 1 billion

    mov     esi,0          ; power of two (LO DWORD)

    mov     edi,1000000000 ; 1 billion loop limit

    mov     ebp,0          ; power of two (HI DWORD)

 

startloop:

    inc     ebx                                  

    mul     ebx

    jnc     K4             ; You don’t need to do shrd at all

    bsr     ecx,edx        ; Bit scan right put result in cl (ecx)

    bt      eax,ecx        ; Check highest bit among the trimmed away ones

    jc      K2             ; Jump to the procedure where we increase EAX

    inc     cl

    shrd    eax,edx,cl     ; Shift right cl number of bits from EDX to EDA

    jmp     K3

K2:

    inc     cl

    shrd    eax,edx,cl

    inc     eax

K3:

    add     esi,ecx

    jnc     K4

    inc ebp

K4:

    cmp     ebx,edi        ; do we have 1 billion yet?

    jne     startloop      ; jump if not equal to startloop

    exit

main ENDP

END main

 

 

 

På bara 16,9 sekunder får vi svaret i hexadecimal form: A59E8867 * 2 ^ 6A0079F06 vilket decimalt motsvarar  ungefär 9,904 * 10 ^ 8 565 705 522. Visserligen har de båda andra programmen större precision men vill man prioritera rå snabbhet så kan man säga att C# och C++ suger. Assembler äger!

 

ET phone home – låt din laptop ringa hem och berätta när den blivit stulen

Tanken har slagit mig flera gånger att det vore smart att låta datorn skicka ett litet meddelande och berätta var den är så fort den blir ansluten till internet. På så vis skulle en eventuellt stulen dator kunna avslöja var den befinner sig. Men det visar sig att det finns fler som tänkt på denna idé och det saknas inte kommersiella tillämpningar. För något år sedan läste jag t.ex. om en student i Lund som hade installerat ett sånt s.k. spårningsprogram på sin laptop. Datorn blev stulen och polisen kunde sedan med hjälp av IP-numret som datorn hade skickat iväg gripa tjuven på bar gärning.

Det låter ju smart, eller hur. Varför har inte alla det på sin laptop, undrar man. Jag undersökte marknaden och fann att Dustin Home t.ex. säljer 3-års abbonemang på en produkt som kallas Smart Tracer. Det som fick mig att hicka till var priset: 4595 kr eller 187 kr i månaden! Visserligen så kunde man använda produkten till 5 datorer, men ändå! Vad är det man betalar för? Varför ska man betala 187 kr/mån för att ha en liten process på datorn som då och då skickar några bytes med info till en hemsida. Hutlöst. Jag vill inte betala något alls så varför inte göra ett eget hack. I går kväll skred jag till verket. C Sharp kändes som ett bra val av språk. Det borde vara en lätt match eftersom jag flera gånger tidigare skapat program som utbyter information med hemsidor. En viktig pusselbit fattades dock.

Alla program jag skapat tidigare har man varit tvungen att logga in först för att köra men i det här fallet vore det en väldig fördel om programmet skulle kunna ”ringa hem och skvallra” redan innan någon loggat in på datorn. Hur skulle det gå till? Eftersom jag kör Windows på datorn så ligger lösningen i att packetera programmet som en s.k. Windows Service. En sådan Windows Service kan ställas in att startas ”Automatic” vilket betyder att den startas direkt i samband med datorns uppstart. Ingen användare behöver logga in för att den ska funka. Nu, tjugofyra timmar senare, sitter jag här med min egen färdiga Windows Service som jag kallar ETPhoneHome. Nu är det bara att vänta på att datorn blir stulen så ska tjuvarna få se på andra bullar. Om internetuppkoppling för tillfället skulle saknas så försöker programmet om och om igen ända tills det får kontakt. Denna process är helt osynlig. Ingen märker något.