david wong

Hey! I'm David, a security consultant at Cryptography Services, the crypto team of NCC Group . This is my blog about cryptography and security and other related topics that I find interesting.

Toom-Cook multiplication for dummies

posted April 2014

We're learning a lot of algorithm in my algebre et calcul formel class. One of them is the Toom-Cook algorithm used for multiplication of large integers.

I found a super simple explanation of it on a forum, it helps:

Say, we want to multiply 23 times 35.
We write,
p(x) = 2x + 3,
q(x) = 3x + 5.
We are using our realization that any integer can be written as a polynomial.
Here, p(x), represents 23, and q(x), represents 35, when x equals 10.
We write,
p(x)q(x) = r(x).
That is, p(x) times q(x), equals r(x).
So,
(2x + 3)(3x + 5) = ax^2 + bx + c = r(x).
Now,
p(0)q(0) = r(0).
So,
(20 + 3)(30 + 5) = a0 + b0 + c.
Therefore,
c = 15.
Now,
p(1)q(1) = r(1).
Therefore, when we do the substitutions (for x and c),
a + b = 25.
Now,
p(-1)q(-1) = r(-1).
Therefore, when we do the substitutions (for x and c),
a - b = -13.
Now, we already know c, and we just need to find a and b.
We have two linear equations and two unknowns,
a + b = *25,
a - b = -13.
We just add the two equations and we get,
2a = 12.
Therefore,
a = 6.
Now, we can substitute 6 for a in,
a + b = 25,
and we get,
b = 19.
So,
r(x) = 6x^2 + 19x + 15.
Now, we substitute 10 for x in r(x), and we are done,
r(10) = 600 + 190 + 15 = 805.
Believe it or not!

2 comments

Why can't I copy PS3 games and play them on another console?

posted April 2014

I've always wondered how it is that we can't easily copy the entire content of a CD/DVD/Bluray on another one and play it with a PS1/PS2/PS3 and I guess PS4 and its competition.

Here's part of an answer on psx-scene's forum:

Whenever you insert a disc (bluray one that is) the ps3 drive will look at a special area of the disc called the Pic Zone (the BD ROM Mark is actually used in movie discs but not in game unlike what I first thought).This area cannot easily be dumped (you'd pretty much need a bluray drive with a hacked firmware) and of course that specific area cannot be burned on any kind of discs or with any kind of burners commercially available.

reading this made me apply to Sony for an internship :)

comment on this story

Weblang

posted April 2014

I've been writing html, xhtml, and now html5 for ages. I think I started in 2001 (13 years ago).

I had to go through <br> becoming <br /> becoming <br> again.

I had to go through different doctypes

I had to go through new divs like <header> and <footer>

But I never had to go through a syntax change. Why is that? I don't understand why HTML is a language based on tags. It is unnecessary and it just adds time and confusion to typing in html. I haven't ran into any project directed at changing that syntax. And I thought, why not doing it myself? (and if there is already such a project please tell me!)

So I thought about a new language to write static web pages called web or weblang. No tags. Indentation. Simple doctype.

A simple index.web would looks like that:

\web:1 // this is a doctype

\head

$title: 'Weblang example';
$css: 'css/app.css';

\body

$header .monheader{
    $h1 "Weblang";
}

$section #introduction{
    $h2 "What is Weblang?";
    $p "Weblang is an elegant way of writing static webpages"
    "HTML is annoying to write." // there will be a breakline here
    $p{
        what about just writing text like this,
        it's kinda easier
    }
}

// what about just writing text
This is a text block, it will just render as text
in this text I want a list here : $ul{
    $li "with text in it";
}

$ul .links{
    $li{
        $a "more info" href: 'https://github.com/mimoo/weblang';
    }
    $li $a{
        tags can be chained
    }
}

$javascript 'js/jquery.js';
$script 'js/script.js' type: 'javascript';

This is just a first draft. The biggest problem is that plain text and code is mixed. The trick I used here is to use $ to tell the render engine that it is not plaintext. Might not be super clever. I need to brainstorm a bit more about this.

Also I need to look at sass' code to see how a compiler works. Seems to be a bunch of regex.

2 comments

Berlekamp & GO

posted April 2014

I knew that my principal cryptography professor Gilles Zémor was a GO player.

Which is pretty amazing in itself :)

But this keeps going on.

I have an algebra class this semester, and I'm trying to understand Berlekamp's algorithm. Trying to find videos on youtube about him I discover that he is as well a go player! And doing researches about the game at that! So cool :D

comment on this story

Ruby, Go, Rust

posted April 2014

I've been planning to code my next web project with Ruby on Rails.

But two languages have also been catching my attention. Go and Rust.

And today, I ran into two wonderful websites:

Those websites are so pretty that it just makes me want to read them! Great complement to learnXinYminutes.

Now I just have to find a project to code with these languages =)

comment on this story

Using Google, Facebook (and others?) to DDoS any websites

posted April 2014

chr13 has posted a nice finding on how to DDoS a website thanks to services like facebook and google.

It's actually pretty simple!

You just create notes with img tags, facebook will crawl the website to cache the picture.

In his example he writes a thousand img tags per notes, opens all the notes from several browsers.

<img src=http://targetname/file?r=1></img>
<img src=http://targetname/file?r=2></img>
..
<img src=http://targetname/file?r=1000></img>

Thousands of get request are sent to a single server in a couple of seconds. Total number of facebook servers accessing in parallel is 100+.

The funny thought of facebook DDoSing itself crossed my mind. Interestingly someone else's also and chr13 answered that he hadn't tried:

It’s against the bug bounty rules to do this, hence one has to be careful here. I was only using browsers at first just because of that.

comment on this story

Slides with LaTeX

posted April 2014

If you read this blog, you know that recently I gave a talk on bitcoins.

I also gave a talk on whitebox cryptography last week.

One part of giving a talk that a lot of people tend to overlook is making good slides. I've always used Powerpoint for that, but for my last talk on whitebox cryptography I had two other persons on my team. Powerpoint was not an option if we were all working on the same file. LaTeX is the solution.

It's a real text file so you can use a revision control system like git, it's constant in its layout. You configure it at the beginning of the file and then you don't have to worry about it later.

We also had a fight (we were tired) on what theme to used. I went for no theme at all. Because everything else is visual noise.

Here's a great article from Zach Holman on the subject. If you ask me, and I'm not saying my slides are perfect, there are way too many crappy slides out there!

comment on this story

SSTIC 2014

posted April 2014

Symposium sur la sécurité des technologies de l'information et des communications is a 2 day con about security. Entrance is 260€ or 60€ if you're a student, still quite expensive, there seems to be a way of getting a free pass: analyzing a usb trace and extracting a mail from it.

Here's the trace.

translation:

Hello,
here's a usb trace I got from plugging my brand new android to my personnal air-gapped computer.
I'm suspecting that a malware is on my phone. Could you check?

So where do I start...

comment on this story

Lundum Dare about to start

posted April 2014

The Lundum Dare is starting in a bit less than 10 hours.

Ludum Dare is an Online Game Jam event where people from around the world create a game in a weekend.

You have 48 hours to produce something good! In what language? I used to watch notch do it in java, but apparently you can do it in whatever language you like.

To reach more participants, web entries are best (Flash, Unity, Flixel, Flashpunk, HTML, etc). They’re quick to start playing, and cross platform.

I need to get into Unity a lot more to get into that kind of contest. Every year I'm telling myself "next year I'll do the lundum dare"....

comment on this story

Nodster day 3

posted April 2014

I can't stop coding this thing. What I've done today:

  • This is the query I'm using in google now : [your search] mp3 -facebook -youtube -soundcloud -last.fm -amazon -dailymotion -bleep
  • I'm now parsing google and the following links with jQuery: $(body).find('a') and then looking for good links with a regex. This is so much more quicker!
  • There is still a part that is taking some time though, it's the metadata fetching. I still have to get every mp3 independently and download enough bits to learn its metadatas...

But it is working quite well as it is!

EDIT: I'm now fetching the metadata in parallel and it's super fast! I've also fixed a ton.

comment on this story

Nodster day 2

posted April 2014

Okay. I'm not gonna talk too much about my new node-webkit project Nodster because I also have a lot of studies to do (exams next week!).

nodster

The problems

  • I'm still not streaming the mp3s properly. I think that I'll never be able to do it through the html5 audio and I need to look up other solutions. The do it yourself approach seems appealing and I'm gonna look into node speaker and node lame.
  • I'm using node google to crawl google and get links. It's not working properly and I'll have to dig into crawling google myself.
  • I'm parsing pages with a regex, it really seems to be slowing everything and I'm gonna look into using a dom parser. I heard about cheerio, is it good?

What does the app do?

  • Right now it's crawling google and avoiding useless websites like youtube, facebook, soundcloud, etc...
  • Then it goes one step deeper and looks for .mp3
  • It checks each mp3 for size (thanks to the headers) and download a bit of each to get metadata.
  • Displays the metadata and a link to play the file
  • If the link is clicked, the mp3 is downloaded to a buffer.mp3 and played.

The main problem is that it's slow, and it's not finding enough links. I could try to parse bing, yahoo and a list of mp3 finders. Or I could maybe try to optimize the requests to google...

Anyway, this app is bringing me a lot of problems to solve and it's pretty interesting :) some people have already forked it and someone has already requested a pull, so if you wanna help. Come and fork it!

2 comments

Nodster (node-webkit)

posted April 2014

As always when I have to study for exams I find a gazillion other things to do.

Last night I downloaded node-webkit. I've been slacking when doing QT and WxPython because they were boring. And I thought that node-webkit would be as well. One hello world later and I was amazed at how easy it was to create desktop application with it!

Spent my day trying to figure out what are pipes, streams, websockets... I have to admit I have a long way to go but I really enjoyed this session of node.js.

I had this idea of a free spotify that would just get mp3s from google. There are a lot of legal issues around so I'm wondering if I should really keep this one, but here is what I did today: Nodster (Node-webkit + Napster).

nodster nodster2

The code is not pretty as I was trying and discovering new things all along. The design is crappy but this is obviously because I had other better things to code first :) I want to get the metadata of the mp3s to sort them more easily (most of them seems to have metadatas) but I have trouble figuring out how to do it.

Also it uses mp3skull.com to find mp3s, there are a lot others but eventually I wanted to just use google and crawl hard.

I could also add pictures for albums and... so many things to do!

If you want to help, fork away :)

2 comments