Thank you.
I'm David.
So I started using scratch
when I was 11 years old, and I wasn't very good at it back then.
I was doing more of the cat spending on the spot that was mentioned earlier,
But now I'm back 13 years later
with a bit more programming experience under my belt.
Kind of returning to my origins to see what I can actually do with Scratch now.
So by day, I'm a security researcher,
especially in software reverse engineering.
I'm particularly interested in file formats, protocols,
serialization and parsing and lots of other things.
And I also enjoy breaking weak cryptography,
but I'm not a cryptographer or a mathematician.
So my mathematical knowledge is actually pretty weak.
So this might be interesting for other people in the same boat
as to kind of see how I get by without actually understanding some of the maths.
So the first thing that people ask when I tell them that I've implemented
some photography in scratch is that like, why, why on earth have you done this?
But why would you do that?
And the first answer, and the shortest answer is because I can.
And that's the only answer, really.
I felt like I had to make up some other answers
after the fact, because otherwise I'd seem a bit insane.
So one answer is that as a reverse engineer,
it's all about spotting patterns in code to figure out what it's doing.
And the only way you can spot a pattern is if you've seen it before.
And the best way to say it before is to implement the algorithm yourself.
So by implementing algorithms from scratch,
it improves your reverse engineering skills.
And implementing things in scratch is kind of an added level of difficulty, really.
And it means you can't cut any corners.
You really do have to implement everything from scratch with no
no cheating, using libraries and things like that.
The next reason is that I want to demonstrate that
cryptography isn't like this magic black box that does stuff.
You can actually construct it yourself with quite primitive,
primitive components like scratch.
And finally, I'd like to show that scratch is a real programing language
because a lot of people like to say it's just a toy.
It's not a real programing language,
but it's really no reason that it wouldn't be a real programing language.
You can do anything in scratch that you can do with a computer.
It might just be a bit more tedious.
So my goals for this project
is to have like reasonably fast cryptography, scratch it.
So is quite a slow language.
It's interpreted and the interpreter runs in JavaScript.
So there's like a lot of layers of slowness going on,
but I don't want to be waiting all day
for a small message to encrypt, so I want it to be reasonably fast.
And of course,
I want it to be reasonably secure, but I probably wouldn't rely on it anyway.
It is more of a prototype than something you would actually want to use.
And finally, I really want it to be correct.
So I want my implementation to match the specifications to the letter
so that if I encrypt something in scratch, I could put it into Python
and decrypt it in Python so that it is compatible with other implementations.
And finally, what do I mean by modern cryptography?
Because that's a bit vague, deliberately so, but
for my project, I want to have standardized
standardized ciphers that are actually used in the real world,
because I think that makes it more interesting.
And also, I don't want to use any known vulnerable ciphers.
So something like C4 for that you might have heard of is pretty old at this point.
There's multiple published vulnerabilities in it.
So I wouldn't want to use a cipher like that,
even though it'd be very easy to implement and scratch.
So the algorithms that I chose to implement,
the first one
is chapter 20.35,
which is no antiquated symmetrical encryption algorithm.
I'll explain what that means a bit later, But I chose it because it's
secure and fast and it's standardized and it's used in Thales 1.3
and also the x two 5519 key exchange algorithm,
also secure and fast, also standardized and also used in Thales 1.3.
And that's interesting because Thales is what underpins HTTPS used by web browsers.
So every time you load a web page over actually taps at the chance
that your browser is using these same ciphers to encrypt a webpage.
And finally, as a hash algorithm
I implement, I'd like to be also first also standardized
and it's used in Wireguard, which is a very modern VPN protocol.
And one nice thing about it
is it only uses 32 bit integers compared to some other hash functions
and a lot of other functions like to use 64 bit integers, which as I
explain later, are annoying to do in scratch.
Another
reason I picked it is because it shares a lot of code of transparency,
so I can kind of copy and paste a lot of my implementation.
At some point I would like to implement a signature algorithm.
I haven't done that yet, but when I do it will probably be as two 5519.
I don't know how it works yet, so I can't implement it.
But one day I will.
So, so just a quick overview of Chapter 20.
It's a symmetric encryption algorithm, which means that you can encrypt a message
using a key and then decrypt the message at some later point using the same key.
So that might be after you've sent it to someone else,
or it might be saving data to your hard drive or something like that.
And it was published in
2008 by Daniel Bernstein.
And that's interesting because Scratch was published in 2007.
So this is actually more modern than scratch itself,
even though it might seem a bit old in the grand scheme of things.
And it's an example of what's known as an hour X construction,
which means that only users of three or four operations edition rotation and XOR.
And I'll explain what those mean a bit later.
But it's ultimately quite simple only only three things I need to worry about.
And it also, as I mentioned earlier, uses
32 bit numbers which work nicely in scratch.
And it's a stream cipher, which means it works by producing
a pseudo random sequence of bytes based on the key, which it then combines
with the bytes from your message that you want to encrypt using XOR.
So I did say this is from scratch.
So I'm going to start off with the very basics.
How do computers represent numbers?
So obviously as humans we're used to using the digits 049
and then when we want to do numbers higher than nine, we use more digits.
So we got up to one zero as ten as
binary only uses the digits zero at one.
We call a binary digit a bit and there are eight bits and bytes
and commonly you'll see other lengths of numbers
are 32 bit for example, or 64 bit or even more
frequently used in computing.
So before I give an example of binary,
just I will remind you all
how decimal works because you kind of take it for granted, but
you've got the number 137 on the left there.
The first column is kind of worth 100.
The second column is worth 30 and the last column is worth seven.
And if you add those three components together,
you end up at the number 137.
And so binary is exactly the same concept, but we've just got zeros and ones.
And so in this example, the number 137 is 10001001.
The first one is worth 128.
The next one is 12 eight.
And the last one is one.
And if you add them together, you will also get 147.
So hopefully you can see how that kind of translates conceptually across
and obviously,
I said Joshua, 24, was an error X construction.
So we've got additional rotation in X
and obviously the first of those three is addition.
And that's exactly what you'd expect it to be, except
there's one catch because we're dealing with 32 bit integers.
You can only represent numbers less than two to the power of 32,
otherwise you run out of bits.
So what happens is when a computer adds two separate numbers together,
if the result is too big, it just kind of chops off the high bits
which results in it, wrapping around to a smaller number again.
So for example, if I had
the number, that's one less in search of the path.
MP two and then I added one,
I would end up back at zero or if I added two, I would end up at one.
So that's called wrap around.
So the next two for three of our axes rotation.
So for
rotation, you, you look at the bits of your free number.
In this example, I've got 23, the number 23 in bits
and you shift all the bits one way or another.
In this example, I'm shifting to the left by one.
So all digits move to left by one and then the digit
that would kind of fall off the end comes back round to the start.
And if I was shifting by two or three then there'd be two or four digits
wrapping around back to the start.
So in this example, I had 23.
I shifted that for the left by one, rotated it, the left by one given,
and the resulting bits are equal to 46 as a decimal.
And finally we've got XOR.
So fundamentally XOR is a function
that takes a pair of bits as inputs and outputs one bit.
If both of the input bits are the same, then the output is zero.
And if they're not the same, then the output is one.
And bitwise XOR, which is kind of what I mean
when I say XOR in general is where you have two numbers.
You take that bits and you apply that XOR function to each pair of bits H number.
So in this example I've got seven being excited before
and you can see how in the first column
I've got 000 becoming zero because they're about the same.
And in the last column you've got one being zero zero
becoming one because they're different and that results in 0011
at the end, which is equal to three, so seven x or four.
And this is all in this example is three.
And obviously there's only four bits in this example,
but the exact same thing is done with 32 bits
as part of the 29. Now.
So with those three co operations adding rotate, rotating
and so they're combined together to make the whole cipher.
So Jojo 20 has 16
1632 bit integers
called the states and they're arranged in this 4x4 grid.
Now the key is only 256 bits or 30 bytes,
but there's 512 bits for states.
So the key only occupies half of it and it occupies the middle two rows
split up into 32 bit chunks for each number.
Now at the top row we've got this phrase.
It says Expand 32 byte K split
across four four words.
And what that is, is an example of a nothing up my sleeve number,
which cryptographers call them.
And that's basically just an arbitrary, completely arbitrary number.
And that's their way of proving that they're not doing anything sneaky
with that number.
It is purely an arbitrary number.
They're not trying to introduce any vulnerabilities into the cipher Somehow
way. And on the lower row you've got the counter and the nonce.
The nonsense quite important.
It has to be unique for every message that you encrypt.
If it's not, then you end up with the cipher being vulnerable
and you could potentially crack some or all of the messages.
And there's also the counter, which I'll explain in just a bit.
So, yeah,
so once you've got the site state set up,
there are 20 rounds, hence the name chatter 20.
And in each round, something called the quarter round function
is applied to the columns of the states
or rather on every other round.
It's applied to the columns on ones, on the other rounds
it's applied to the diagonal columns.
So that quarter round function looks like this.
This is the same function represented in two different ways.
So on the left we've got a kind of pseudocode representation.
It's not quite valid syntax, but it's close enough.
And on the right we've got this kind of I should note the name of this diagram is,
but it's a, a diagrammatic representation of the same operations
where the yellow box represents addition.
The blue circle is X0 and the green, the green box is rotation.
So you do 2020 rounds of that
and then finally you add
the initial state into your current state.
The reason that's done is to make sure that the cipher isn't invisible.
If that wasn't done, you could kind of undo the quarter
round functions and derive the key.
So that's quite an important step there at the end.
So finally, after all that's been done, you've kind of you've randomly mixed up
all the old data that was in your initial state
and I've got your pseudo random values
and this is what you xor with your message that you're trying to encrypt
and to decrypt it again, you are with the exact same,
the exact same data and you end up back where you started.
Because something I didn't mention earlier about XOR is
that if you XOR two things together and get the results
if you xor the result with one of your inputs, you'll always end up
with the value of the other input, if that makes any sense.
So XOR is kind of reversible like that.
So enough enough cryptography theory.
Now it's time to talk a bit about scratch.
So I'm sure you've all heard of scratch at least to some extent,
but you might not realize quite how popular it is.
There have been over 100 million projects shared on the scratch websites.
And by contrast, GitHub has about 150 million
public repositories, which is of course more, but is not very much more.
And I would have never have guessed they were in the same order of magnitude.
And scratch is open source, which means I don't use reverse engineering.
Fortunately, the source code for that runtime is on GitHub,
so you can look at how their internals work, which is very useful.
And I'm just going to give a quick demo
of like the capabilities of Scratch won't take very long, hopefully.
So I've got a little test project up here on the on the right here.
You've got your sprites and you've got your stage.
The stage is where the
sprites of positions and on the left hand, you've got your scripts.
So you write, you write code by dragging these blocks around
and you've got all the standard control flow
that you'd expect from any other programing language. You've got loops,
you've got if statements, you've got variables, you've got lists,
and you've got basic mathematical functions,
addition, subtraction, etc..
And yeah, I'll just make
I'll make the count spin around since we were talking about that earlier.
Um, there are
there you go.
So that's just an example of the kind of things you can do in scratch
in your own use.
So scratch,
although in theory it can do anything because it's Turing complete
and it has quite a lot of limitations when it comes to trying
to implement cryptography.
So run.
It's all the numbers in scratch
because it's running on the JavaScript under the hood.
They're all 64 bit floating point totals.
And I'll explain.
Sorry, 64 bit double precision floats, even.
I'll explain what that means in detail a bit later,
but it's not effective integers, so we can't just
drop in the algorithm and have it work.
It also lacks X or electrodes, which might sound like a bit of a problem,
but I'll go into how I address those shortcomings in just a bit.
And of course, you've got to use your mouse
making longer scripts gets very tiring.
Like you've just got to do
miles and miles of dragging to get your blocks into position.
And it's very tedious if you're a fast touch type in comparison.
And also there's no version control.
When I write code, normally I'm very used to committing it to get,
and when I can't do that, I feel pretty lost and feel like I'm about to lose.
On my changes at any point, which of course you can. So
before I get into how I overcome those difficulties,
I will explain how floating point numbers work so well.
So you, as I said, scratch as variables are stored as floating point numbers.
And if you're familiar with scientific notation in physics,
it's a very similar concept.
So rather than writing that the speed of light is 300 million
meters per second, we write three times ten to the power eight
and floating point numbers are basically exactly the same concept.
You've got the exponent, which is like the green section of that diagram
and the fraction, which is the red section of that diagram.
And so in the speed of light example,
three would be the fraction, an eight would be the exponent.
And there's one extra bit
that says whether it's a positive or negative number or not.
So that can represent like arbitrary numbers.
So you can have fractions, you can have really big numbers.
But there's one catch
if your integer goes above.
So it's the power of 53 because there's 52 bits for the fraction.
If it goes above that, then you start losing precision.
And what that means is the accuracy of your
your maths will start to drift from the correct values,
which is a big problem if you're trying to do something precise like cryptography.
But fortunately, because
32 bit numbers only go up to two to the power 32,
that's actually not much of a problem for 32 bit numbers.
As long as we make sure that we keep keep our numbers rounded to whole numbers,
we won't run out of precision.
So the next the next challenge is bit was XOR
and of course Scratch has no active operator, but
as a bit of a cheat, we can make a list of every possible result.
So we can make we can make a list of every pair of numbers.
And what the result is if you hold them together, every pair of numbers that is.
And so the list for eight bit numbers is 65,000 entries long.
So of course I wrote a Python scripts to generate that list
and then
you can you can implement that and scratch like so in there.
So scratch lists are only one dimensional, but we kind
of got a two dimensional table here.
So there's a little bit of arithmetic to, to convert the indexes
and let's just has a plus one on the end because scratches lists
start counting at one instead of zero, which is a bit annoying if you're used to
it being starting at zero.
Now that's for eight bit numbers.
But for chapter 20 we need to XOR 32 bit numbers together
and this is where it gets a bit crazy.
So we need to split our 32
bit inputs into eight bit chunks
and then we xor those chunks together separately using the lookup table
and then we recombine them into 132 bit results.
And the methods for
splitting the numbers up is called shifting and masking.
So shifting is very much like
the rotation that I mentioned earlier, except the numbers that fall off the end.
You don't bring them back to the start, they just disappear.
So shifting left is actually equivalent to multiplying by a power of two.
So five shifted left by two is the same as multiplying five by four
and conversely five shifted right
by two is the same as dividing five by four.
But you need to round down once you're done.
Otherwise you would end up with a fraction number at the end.
But you actually you want a whole number at the end.
So if you round down five divided by four, it's
exactly the same as doing a bit shifts right by two.
And that can be done in scratch very easily.
So we have
the XOR lookup tables, the shifting and masking.
Oh, I actually haven't covered masking yet.
So masking is quite a common operation.
You do in bitwise logic if you want to extract some portion of a number.
For example, the last eight bits you might end up with 255,
which what that essentially means is
you extract the last eight bits at a number,
the scratch doesn't have a bitwise and operator, but in a pinch
we can use the modulo operator, which fortunately it does have.
So if you take a number and you put it modulo 256,
you extract the last eight bits of the value.
And for example, if I wanted to get the second last eight bits,
I could shift it first and then do the modulo and I would get the eight bits
that were the second, so the second lot of bits of the number.
So combining all that together with if.
XOR Yeah.
XOR masking and shifting, you have this horrible abomination of scratch code,
it doesn't even fit on one slide, it's going off the off to the right.
If I zoomed out all the way and it still wouldn't fit.
So as you can see, this is pretty unwieldy.
So I didn't want to have to write a whole program
with hundreds of blocks like this.
So I decided that I needed to automate this process somehow.
So I'm sure you've all seen the XKCD comic
about some writing, writing tools.
You'll always spend more time
writing the tools than you do spend actually using them,
and you'll probably never finish them either, which is very true,
but I still did it so.
So scratch scripts when you save them to a file
they are, they're stored inside a file called with Don't SP3
extension, which is basically just a zip file in disguise.
And inside that zip file is adjacent file, which contains a list
of all the blocks in your scripts
and that contains all the attributes, like what their arguments are,
what their position is, and what other books they connected to.
So rather
than dragging and dropping books around to the mouse, I could, in theory,
write some code to generate this Jason file with all the blocks already in it.
And that's exactly what I did.
I made a Python library.
I called Boyega
for generating a scratch code.
Now, the reason I called it
that is because there's apparently a species of snake called Boyega
Crostini, which supposedly is nicknamed the Cat Snake.
I'm not quite sure why, because I don't see the resemblance myself.
But that's why. That's why I picked the name.
Because the scratch mascot is a cat, and the Python logo is a snake.
So you put the two together and you've got a Boyega.
So this this library that I made is is a bit weird.
It's not quite converting Python code to scratch code.
What it is, is a library for expressing scratch
syntax, a scratch code for Python syntax.
So it's actually more powerful than translating Python into scratch
because you can, you can
write a program to generate other programs
or something.
So I'm just going to show you a quick example.
So with that horrible XOR example I showed you
before can actually be
implemented fairly concisely
in Python.
This might look more complicated, perhaps, but it's much easier to work with
because you don't have to drag and drop million books around. So.
So this is an example of co-written with the library
here.
Actually, I might zoom in a bit so you can see it, but
okay, so here
I'm declaring to scratch variables
and I x
all of them together and make the cat say the result.
And here I'm doing all the shifting and masking and lookup tables
and I talked about earlier
and it's all implemented through Python syntax
and you'll notice that I'm using the Python bit shift operator here that is
under the hood
translates that into the scratch books, just like I described earlier.
And if I run my script, which hopefully still works,
exploit it, um, open up around the scripts
and if I open that in scratch.
So this code was just generated by that script that I just ran.
And if I, if I click that green flag, I shall make it full screen.
I see the scratch that says Hello World.
And then Axel's two numbers together and tells us the result.
So? So
now that I can write scratch code much more easily, effectively in Python.
The sky's the limit. Really.
So this, this is what I came
up. So.
So what you're looking at
here is all the almost life, as I mentioned in the initial slide.
So we've got the Cheshire Cat of 20.35, we've got the
go to go now go to hashing
and we've got the x 5519 key exchange algorithm.
Now, I wish I had more time to explain what every bit of this does in detail.
So everyone I find me afterwards and ask me, but for now
I will just show you it working because I think it is very cool.
So the code, the code for that you just saw on the screen
that was generated by this Python script and it's actually pretty short.
There's only 24 lines of typing in this file, but it's all calling
into libraries that I wrote again, using using this library.
So I've I've effectively written a cryptography library from scratch
that you can use with my tool to embed cryptography within any scratch projects.
And so if I generate the scratch code just now
and open it and scratch
it takes a little bit to it
because there's almost 4000 books in here.
But I'm just going to I'm going to shrink that down a bit.
And Scratch has this handy function code, clean up books that artfully arranges
your books into a joint list.
So I can I can scroll for
that.
But actually, if we get down to the bottom,
we've got this is like the main the main loop effect or the main function even.
And if I, if I Zaman is doing fairly readable things.
So we've got some C
where I'm initializing a random number generator,
we're getting some random bytes, we're performing an X to 5519
scalar multiplication, which is part of the key generation process,
etc. etc.
So now I will show you actually doing something.
So here we go.
Sorry, just Jennifer, what I just did here is it generated
a next two 5519 keeper.
It generated a public no, it did a different human key
exchange against public here that I embedded within the program
generated a shared secret and then encrypted a message
or sorry derived the session key from the shared secret.
And now if I type something in here like hello,
it encrypts it very quickly.
And I'm sure you just noticed that was like a blink of an eye.
So I'm quite glad that it was it was that fast after that.
And also, obviously in this demo, the key is being printed on the screen.
You probably wouldn't want to do that in any real application.
So if it if anyone if anyone wants to try decrypting this message,
you should be able to use standard, standard tools to decrypt it.
So yeah, that's it.
Thank you for listening, everybody.
Give it up for David Buchanan.