## Finite Fields, or Some Notes on Why I Love Math! — Part I

### History

In the process of applying for my research fellowship, I had a phone conference-interview with the people there. One of the things that we talked about was about cryptographic schemes that distribute parts of data between, say, $n=100$ nodes, in a way that the data can only be read if at least, say, $m=10$ of those $n$ nodes come together; for instance, you have a bank with 10 managers and you, as the owner, don’t trust them enough to give each one of them a key to the vault, so you want to deploy a scheme that lets them open the vault only if at least 3 of them are present 1. Since long ago, I knew a trivial answer to this problem for $m=2$ 2, but adding to $m$ is not easy in my solution.

So I looked in my copy of Applied Cryptography book 3 and found a few solutions. Among the solutions two of them caught my attention, one by Karnin-Greene-Hellman that used Linear Algebra (and I’d love to write about in the future), and another one by Adi Shamir, hence its name, Shamir’s Secret Sharing scheme, that deploys polynomial equations and LaGrange’s interpolation algorithm, which I’ll explain in the next section.

### Introduction to the Solution: Shamir’s Secret-Sharing Scheme (aka. LaGrange’s Interpolation Polynomial Scheme)

The solution was to first generate a degree $m-1$ polynomial equation and call it $K$. Now, as those of you who remember quadratic equations know, if I give you 2 points in a plane, you can give me a line — a first degree equation:

Image from Cornell.edu

In the picture above 6 points from the line are shown, but only two of them are enough to find the exact equation of the line. Similarly, if I give you 3 points, you can give me a quadratic equation, or a degree 2 equation:

Image from Cornell.edu

To generalize, if I give you $m$ points, you can give me a degree $m-1$ polynomial equation! Got it? Each share is a point in the graph of $K$, and since $K$ is of degree $m-1$, at least $m$ points — one for each of the $m$ key-holders — are needed to find the line $K$ — aka. the key! Sounds easy, right?

### The Problem with the Solution

The problem is that a strong polynomial equation for this scheme have integer solutions, and of course, it’s hard to work with non-integers in computers; you know, floats are a mess! So basically I ignored this solution and only worked with the Linear Algebraic one; but little did I know about how smart the idea behind using this polynomial equation solution is!

### The Solution to the Problem of the Solution (!): Parallel Math Worlds (aka. Finite Fields)

Disclaimer: the following section is intended for non-math people; I’m a math major student and when I explain this idea to a math-friend I do it right, but hey, this is just a blog post!

Suppose we live in a world where the biggest number possible is 4! The ONLY numbers you can use are $\{0,1,2,3,4\}$. We call that a finite field or a cyclic group of order five and denote it as $\mathbb Z _{5}$ 4. Now, let us say we live in this $\mathbb Z _{5}$ world; how do you think kids learn math in such a universe? First we need to teach them a modulo or modulus operator:
Let us define a simple division:

$a=b\times k + q$

$a$ is the nominator, $k$ is the denominator, $b$ is the integer solution of division, and finally the one that we mostly interested in: $q$ is our remainder. Now we define modulo operator $\bmod$ as:

$a\equiv q \bmod k$

Got it? Simple as that! So what else do they learn in school?

• First thing they learn is addition, of course:

$a+b\equiv c \bmod 5$
e.g: $2+4\equiv 1 \bmod 5$

• Then, in subtraction, in order to solve $a-b \bmod 5$, we need to find $d$ such that:
$b+d\equiv 0 \bmod 5$

Then we can say that:

$a-b=a+(-b)\equiv a+d \bmod 5$

$a-b\equiv a+d\equiv c \bmod 5$

For instance, since:

$2+3\equiv 0 \bmod 5$

We work $1-2 \bmod 5$ out as:

$1-2=1+(-2)\equiv 1+3\equiv 4 \bmod 5$
• Next they learn multiplication:

$a\times b\equiv c \bmod 5$
e.g: $2\times 4\equiv 3 \bmod 5$

• Similarly for division, in order to find $a\div b \bmod 5$, we need to find $d$ such that:
$b\times d \equiv 1 \bmod 5$

Or:

${1 \over b}\equiv d \bmod 5$

This idea of calculating the reciprocal of a number in $\mathbb Z _{5}$ is quite interesting for me, you’ll see why soon. Using it, we can say that:

$a\div b=a\times b^{-1}\equiv a\times d \bmod 5$

Now since we already know multiplication:

$a\div b\equiv a\times d\equiv c \bmod 5$

For instance, since:

$3\times2\equiv 1 \bmod 5$

We work $4\div 3 \bmod 5$ out as:

$4\div 3=4\times 3^{-1}\equiv 4\times 2 \equiv 3 \bmod 5$

Note that not all numbers in a group are invertible. We’ll get to this later.

• Next big thing is exponentiation and finding e-th root. I’ll get to e-th root for $latex 2 $2^3=8\equiv 3 \bmod 5 \\ 4^2=16\equiv 1 \bmod 5$ $\sqrt{1}\equiv 1\bmod 5 \\ \sqrt{1}\equiv 4\bmod 5$ (because $16\equiv 1\bmod 5$) I think that’s enough for now. For the record, this is what we call Modular Arithmetic in this world, of course, in the parallel world this is just normal arithmetics! Let us see a wonderful application of everything above, shall we? Here is the question, solve the quadratic equation below: (yes, of course I mean in $\mathbb Z _{5}$!) $x^2+2x-3=0$ Any ideas where to begin? Well, it’s actually not as hard as you think! In fact you can solve it exactly the way you would have done it in this world! Solutions of a quadratic equation are: $x={-b\pm \sqrt{b^2-4ac} \over 2a}$ Just like this world! Except that we need to use modular arithmetic to find x. Enough talking, let’s work it out: $x={-2\pm \sqrt{2^2-4(1)(-3)} \over 2(1)}\equiv{(3)\pm \sqrt{4-(-12)} \over 2}\equiv{3\pm \sqrt{4+12} \over 2}\equiv{3\pm \sqrt{1} \over 2}\\\equiv(3\pm \sqrt{1}) \times 2^{-1}\equiv(3\pm \sqrt{1}) \times 3$ At this point you may say: “Wow! We are about to have 4 solutions!! Because $\sqrt{1}$ has 2 answers in $\mathbb Z _{5}$ and we have two final solutions based on each answer of the square root!” (because of the $\pm$). I thought so in the beginning too. However, if you think about it, even when you are solving a quadratic equation in this world, the discriminant ($b^2-4ac$) always has two square roots: $+\sqrt(b^2-4ac)$ and $-\sqrt(b^2-4ac)$; but since radical is defined to always return the positive root, we have to put a $\pm$ to count for the negative root too. However, in our parallel universe, since we don’t like negative numbers, we add multiples of the group size to them so they become positive, and because of that, in the parallel universe, numbers can have two positive square roots! So technically we could ignore the $\pm$ and just try both square roots and that would give us both answers; so let’s see, in our example: • First let’s try adding $\sqrt{1}\equiv 1 \bmod 5$: $x_{1}=(3+1) \times 3\equiv 4 \times 3\equiv 2 \bmod 5$ • Now let’s try subtracting $\sqrt{1}\equiv 4 \bmod 5$: $x_{4}=(3-4) \times 3\equiv (-1) \times 3\equiv 4 \times 3\equiv 2 \bmod 5=x_{1}$ • See? we have the same solution! Now for the other one: • First adding $\sqrt{1}\equiv 1 \bmod 5$: $x_{2}=(3-1) \times 3\equiv 2 \times 3\equiv 1 \bmod 5$ • Then subtracting $\sqrt{1}\equiv 4 \bmod 5$: $x_{3}=(3+4) \times 3\equiv 2 \times 3\equiv 1 \bmod 5=x_{2}$ Ta-Daah! Now that we have the two roots of the equations, we can factor it as: $x^2+2x-3=(x-1)(x-2)\equiv (x+4)(x+3) \bmod 5$ Now let’s check them, just for the fun of it: $x_{1}^2+2x_{1}-3=(1)^2+2(1)-3=1+2-3=0\equiv 0 \bmod 5 \\ x_{2}^2+2x_{2}-3=(2)^2+2(2)-3=4+4-3=5\equiv 0 \bmod 5$ For my fellow math people: I found it very interesting that the proof of impossibility of a general algebraic solution to polynomial equations of degree five or higher — aka. Abel–Ruffini theorem — uses groups too and I finally gasped the importance of the Galois theory and Galois group! All thanks to a friend of mine, Amirali Moinfar. ### Polynomial Equations in Parallel Math Worlds Now why did I just spend an hour writing about a parallel universe 5? Because this is exactly the beautiful idea that lets us use the Shamir’s scheme in computers without being forced to mess with floaties! If I define my key polynomial in a finite field of order, hmmm, say, $2^{127}-1$ (which, by the way, just so happens to be a Mersenne Prime), then you can generate a key polynomial of any degree with points a 126-bit coordinate system 6. All done without touching any floaties in the process! See? This is when you’ll need to know how to solve quadratic equations in the future! I think that’s pretty much enough for this part …. In the next part I’ll talk about more applications of Finite Fields. So, Dear all-friends-who-think-I-should-have-been-a-Computer-Science-major-instead-of-a-Math-major, I chose Mathematics because at most (but not all) universities, the Computer Science major is designed to create computer *engineers* — yes, even in the ones that have two different majors one for engineering one for science, the courses are almost identical –, but I don’t want to be an engineer! We created computers, but for many people they are slowly becoming a new specie that we have to adapt ourselves with it rather than changing it the way we want. I want to learn about the algorithms and mathematical ideas behind them, potentially change them, not just learn Java and C++! And as a Math major I can do so! Last thing I want to do now is to rant about how poor our education system is … because it actually turned out to be useful for me! It’s a hard thing to debate about; you see, I learned a lot of things that I know in the library of my high school. On one hand, I still find what I learned in school to be useful. On the other hand, I don’t remember a single exam that I didn’t spend the time I was supposed to be studying for it on reading some random book that I borrowed from the library! One thing that I’m sure of is that I don’t rely on the formal education, but I don’t underestimate it either. For instance, why do you think Calculus is the first major math course in college? Because it’s [arguably] the easiest one! There is much much more [interesting] stuff in Mathematics than many people think there is and it’s sad to know that even many college students don’t have any clue about it! Sincerely, M P.S: Again, thanks to Amirali Moinfar for proofreading this post. Also it’s worth mentioning that I used the WP $\LaTeX$ plugin to generate the formulas. I also enjoyed this life saver a lot! Notes: 1. By the way, this is a simple (n,m)-threshold scheme; there are many other secret sharing schemes out there as well. 2. My solution was a basic secret splitting scheme: Image from Cornell.edu Say, you want to split the key $K$, first create a random key $A$ with the same bitsize, then you have $B=K\oplus A$. Now, give $A$ to Alice and $B$ to Bob. If they come together they can XOR their keys and calculate the original key as: $K=A\oplus B$ 3. I haven’t read a lot of cryptography books, but I’ve heard that no other book even compares to this comprehensive introduction to cryptography. 4. In math books you may also find it denoted as $C_5$ or $\mathbb Z /5\mathbb Z$ 5. That reminds me, maybe I can expand this later to write a math novel, like Flatland; I might call it “Finiteland” or something, I’ll see … 6. Ignore this, it’s just a reminder for me: think about how you can involve public-key cryptography with this … the polynomial is the master key which gives each person an X-coordinate that can be the private key and a Y that can be the public key … cool! I should think about it … ## State of Affairs: SURF@Caltech TL;DR: things are surprisingly going good for once. In philosophy, a state of affairs, or (also known as) a situation, is a way the actual world must be in order to make some given proposition about the actual world true; in other words, a state of affairs (situation) is a truth-maker, whereas a proposition is a truth-bearer. 1 Now that you’ve proved to be patient enough … I got accepted for the very cool Summer Undergraduate Research Fellowship at Caltech 2 which is very cool!! As of now I’m buried under a ton of paperwork (agreements ‘n stuff) that I have to sign and submit soon. Then … I have to wait for two months or so before the program starts. There, I’ll be working on a very cool project that involves a variety of things that I have experience [playing!] with, from pure Cryptography (Public Key Cryptography, secret sharing, etc.) to Onion Routing (like TOR), and Linux network and security features such as OpenSSL, SELinux, etc! A friend of mine said it sounds super cool and honestly, I think it is, so much that I may [or may not] be a little worried about how effective I will be there; but, as I said to my friend, it was just a hobby in the beginning, until it got serious! Those who know me closely know that Jux (formerly HelliJudge) is more than just a project for me; it’s a hobby, even more, it’s like a pet! 3 I go back and play with it whenever I get bored! I tweak it, test features, add features, or at the very least, try to engage in an endless theoretic discussion with Hamed about how to implement new crazy features — needless to say, it never ends! Anyway, my point is, I started and [almost] completely ended a [quite] successful project — that I knew almost nothing about — in half a summer, by getting to school everyday, eating lunch behind my laptop while discussing the project with Hamed, and going home right before getting dark while still discussing the project in the bus! Of course I can manage a summer research fellowship that I know so much about already! So, the more challenging it is, the more I’ll gain from it. On a related note, since late January I took an online Cryptography course on Coursera taught by Dan Boneh, who I came to realize to be a pretty famous Cryptography professor at Stanford. It covered a wide variety of subjects from symmetric encryption, data integrity, and public-key encryption, to key exchange. The class ended about a month ago, but it’s been restarted since less than two weeks ago, so if you’re fast enough you can easily catch up without missing any deadlines. The best part was programming assignments that often even included breaking real-life cryptograms! Last note: until now this blog was merely named Cryptanalyst and maybe a little OpenSSL or other security related stuff was mentioned. The main reason being that I simply couldn’t say anything new about cryptography; not yet! But starting from now I want to engage more seriously with cryptography, maybe write about my ideas or just topics that I’m working on. So, to future! M Notes: 1. Wikipedia, what else were you expecting? Stanford Encyclopedia of Philosophy?! Psht! 2. COOL! Right?! 3. Have you seen Frankenweenie? Yeah, Frankenstein’s pet! More like that kind of pet! ## Google Chromebook: Chrome OS, Chromium, or Fedora Linux? Whatever … Dear Sister, Remember that Chromebook that you bought for your birthday a while back? Just thought I’d let you know that I switched to the developer mode and booted up Fedora Linux off of a SD card. No harm done! Here’s a short story of what I think about this whole bizarre [almost] fairy tale. So, Google, being the feudal lord that it is, starts this ambitious project of starting their own Operating System 1 called Chrome OS. Now, call me biased, but I think good programmers MUST have two backgrounds: 1- algorithm and data structure, 2- Unix or Gnu/Linux philosophy; and Google, being the … well, Google(!), has collected all the good ones. 2 So, no wonder why Chromium, the underlying core of Chrome OS, is actually a legit Linux distribution with a kernel and Gnu software and everything! One thing though, Google’s idea of keeping it’s product both safe (secure boot ‘n stuff) and developer friendly is this: you get to choose between security and freedom! 3 “Bizarre”, is the only word that I could think of to describe this idea. However, I think it’s a very good place to start for a better future. Chromium developers have written a truly lovely page on the challenges and possible vulnerabilities of an ideal combination of security and freedom. Long story short, this page from the Chromium developers helped me to switch your laptop to the developer mode. At this point you have a built-in shell called crosh with root access waiting for you; just push Ctrl+Alt+t after you logged in and you’ll see a new tab open up with a prompt that reads: Welcome to crosh, type 'help' for a list of commands. crosh>  Pretty cool, huh? As I’ve thought you before, just type help to get help: 4 crosh> help exit Exit crosh. help Display this help. help_advanced Display the help for more advanced commands, mainly used for debugging. ping [-c count] [-i interval] [-n] [-s packetsize] [-W waittime] <destination> Send ICMP ECHO_REQUEST packets to a network host. If <destination> is "gw" then the next hop gateway for the default route is used. ssh [optional args...] Starts the ssh subsystem if invoked without any arguments. "ssh <user> <host>", "ssh <user> <host> <port>", "ssh <user>@<host>", or "ssh <user>@<host> <port>" connect without entering the subsystem. ssh_forget_host Remove a host from the list of known ssh hosts. This command displays a menu of known hosts and prompts for the host to forget. top Run top. shell Open a command line shell. systrace [<start | stop | status>] Start/stop system tracing. Turning tracing off will generate a trace log file in the Downloads directory with all the events collected since the last time tracing was enabled. One can control the events collected by specifying categories after "start"; e.g. "start gfx" will collect only graphics-related system events. "systrace status" (or just "systrace") will display the current state of tracing, including the set of events being traced. In the Normal Mode you have almost all of these options, except for the latter two. Well, go on then: crosh> shell chronos@localhost /$ id
uid=1000(chronos) gid=1000(chronos)
chronos@localhost / $uname -a Linux localhost 3.4.0 #1 SMP Wed Mar 13 11:38:55 PDT 2013 armv7l ARMv7 Processor rev 4 (v7l) SAMSUNG EXYNOS5 (Flattened Device Tree) GNU/Linux Ta Dah! And that’s not all of it: chronos@localhost /$ sudo -i
localhost ~ # id
uid=0(root) gid=0(root)

I know, right? A beautiful laptop with Linux pre-installed and no hardware issues! 5 Love you Google! Keep up the good work!

Now, when did Fedora come in? About a week after all that, I saw this and this post on Google Reader 6. They are pretty self-explanatory. May I stop here? I’m very tired an it’s 3:29AM! Oh, one more thing, I know that you are learning Python programming on a Raspberry Pi, Fedora on Chromebook is like a Raspberry Pi with almost four times more RAM, more than twice CPU speed, and, of course, attached monitor, Wireless adapter, keyboard and touch-pad, 16GB SSD, and last but not least, battery! How cool is that? 7 Oh, by the way, Fedoraians also have this page in their wiki about Chromebook.

I’ll try getting Gnome-Shell on it. There shouldn’t be any problems: the ARM package is available, we have enough RAM, what else do we need?

Okay, I think that’s pretty much it.

hope you are well,
Love,
M

Notes:

1. although I refuse to believe that they haven’t silently worked on any such projects before!
2. and that’s probably why most other companies suck!
3. Matthew Garrett believes nobody should be forced to make that choice, and I ought to agree.
4. Again, as I’ve told you before, one out of many superpowers of hackers is that they know WHEN and HOW to get help when they need it, that’s why they can get what they want from any kind of shell. Anyway …
5. Now, don’t tell me that you don’t like this distro, a true Linuxer can manage through any distro what so ever!
6. At the time I’m drafting this post, Google has decided that they will murder Google Reader by the end of July :’( Pray to WWW Gods that they change their mind!
7. It just lacks the GPIO pins, so as long as you are mainly into software (algorithms, etc.) and not hardware (robotics, etc.), it just works perfectly!

## Restarting GNOME Shell using Terminal, or How to use SIGHUP

Recently I’ve been using my laptop for some heavy processing and as a result of that GNOME Shell started to freeze every now and then.
Normally when something goes wrong I try “alt+f2” and then “r” which is a shortcut to restart the GNOME Shell, but when it freezes you can only use your mouse … and go to other terminals!

I’m talking about TTYs, one of the most wonderful features of Unix based operating systems, IMO. It is simply fascinating that you can use one set of mouse/keyboard/monitor to login with more than one user at the same time.

Back to the GNOME Shell problem. The solution is simple: send a signal to whatever process that is causing the problem. If it’s flash player or a game just kill it with SIGKILL or pause it with SIGSTOP, but as far as I know, many Linux services recognize the SIGHUP (signal code=1), including GNOME Shell. You can use kill or killall command to send this signal to programs like this:

# kill -s SIGHUP [pid]
# killall -s SIGHUP [process name]

Here is the description of the signal according to the manual page of signal in section 7:

       Signal     Value     Action   Comment
──────────────────────────────────────────────────────────────────────
SIGHUP        1       Term    Hangup detected on controlling terminal
or death of controlling process

Basically this signal is just poking the process and giving the information with no predefined action (whereas SIGKILL kills the program no matter what), so it’s up to the programmer to define a procedure to be executed in case of receiving that signal.

Fortunately for me, GNOME developers have been kind enough to implement such a procedure that just reboots GNOME Shell without closing child processes (which include all graphical programs!), just as “alt+f2″ “r” does.

That’s it, just don’t kill Linux services, poke them with SIGHUP!

## Android Lockdown, or How to Find the Inner Linux!

What a year! After more than one year, this blog is still alive!

“They besought him of how canst one become so fullsome [as him] in the midst of rude men; Dost as they dost not!, he sweren”

That’s it for now …

[to all the people who are reading this directly, through a feed, through Fedora Planet, through Fedora Planed feed, etc.]
- Hellow! How do you do?

[to anybody who is listening out there!]
- Greetings from planet earth!

When I first bought my Android Samsung Exhibit II smartphone I was mostly interested in working with Android as an embedded Linux operation system and perhaps doing some projects on it; but the Android Debugging Bridge (ADB) shell wasn’t really comfortable and more or less convinced me that it’s not really meant to be used that way. Plus I really don’t like Java so I just forgot about the Linux inside.

[Almost] Everything was going smoothly until a few days ago 1 I got locked out of my phone. Android asks for the connected Google account credentials if someone forgot the gesture code or if someone entered too many wrong codes. The problem is that I had disabled data connection since I don’t have data service, and moreover, I had turned off wifi in order to to preserve battery that morning; so there is no internet access and thus Android could not verify my username and password with Google! 2

My first reaction was to try some special codes such as blank password or 0000, but soon I realized that nothing could be done from outside and the only way was to hack into my phone! Luckily for me, I had left the USB debugging option enabled since I initially tried adb, so getting a shell was as easy as connecting to my phone and running adb.

Since my knowledge of Android internals wasn’t any further than the fact that it’s Linux based, I had no idea of the security methods, controlling the device, etc.. I’m not complaining because I believe that is exactly what makes hacking fun 3

These are my main ideas on how to work around the problem:

### 1- Enable the wireless (iw, wpa_supplicant, etc.)

[Too long, didn't write!] Didn’t work! I had used iw and wpa_supplicant to connect a WRT54GL Linksys wireless router (with OpenWRT installed on it) to another wireless network (yes, client mode!) before, but Android doesn’t have iw on it and apparently wpa_supplicant couldn’t initiate the connection appropriately.
For more information about iw (even though Android doesn’t have it, almost all distros do) and wpa_supplicant Refer to The Respective Manuals. 4
In short, the cool thing about iw is that you can perform network level AND hardware level operations with it, kinda like ip but for wireless devices. A few of useful commands that I use sometimes are:

$iw list # list physical devices # iw dev <devname> scan [-u] [freq <freq>*] [ies <hex as 00:11:..>] [ssid <ssid>*|passive] # scan for wireless networks, just look at all those data! Ain't it fascinating? # iw dev <devname> connect [-w] <SSID> [<freq in MHz>] [<bssid>] [key 0:abcde d:1:6162636465] # iw dev <devname> disconnect ### 2- Connect my phone to internet using my laptop as a gateway (iptables, ip route, etc.) The idea is simple, I’m sure lot’s of you have tried to share internet between two systems at one point before; could be a virtual machine, an embedded system, a PC without wifi card, or getting internet from your 3G phone! As a matter of fact I did succeed to do so with my Android phone, but for some reason the lock didn’t let me in; I could ping Google from the shell, but perhaps the applications can only access internet through predefined ways (wifi and 3G) For more information refer to iptables and ip manual pages. I found this link 5 to be very informative, even though the purpose is different and it’s mainly graphical, it’s for the same cause. ip and iptables are two network related commands that you must know how to work with! Some basic examples: # iptables -L -n # shows current firewall setting # iptables -L -t nat -n # shows current NAT setting$ ip route	# or ip r, same thing. shows the routing table.
# ip r del default
# ip r add default via [gateway] dev [devname]

### 3- Break the lock (resetting the lock, etc.)

Honestly, I didn’t expect this one to work! I mean, seriously, it shouldn’t be so easy to break the lock! But it worked!

[root@eve ~]# adb shell
* daemon not running. starting it now on port 5037 *
* daemon started successfully *
# id
# ls
efs
...
# ls /efs
cryptprop_FailedAttempts
cryptprop_persist.sys.timezone
cryptprop_onetimeboot
cryptprop_securewipedata
cryptprop_lock_pattern_autolock
cryptprop_lock_pattern_tactile_feedback_enabled
dmp
cryptprop_persist.sys.language
cryptprop_rebootMode
edk_p
lost+found
cryptprop_lock_pattern_visible_pattern
cryptprop_essiv
cryptprop_lockscreen.patterneverchosen
cryptprop_applied_result
cryptprop_efs
# mount
...
/dev/block/mmcblk0p27 /efs ext4 rw,relatime,barrier=1,data=writeback 0 0
...
# umount /efs
# 

DONE! The lock is gone! And I wasn’t even root! Apparently /efs is where Android stores many of it’s important properties files, many of which are readable only by root, but anybody can unmount it! This is certainly a security flaw that I’m sure it fixed in the newer versions of Android (mine is Gingerbread 2.3).

Conclusion: But the point of this post wasn’t just to reveal a security flaw after 6 months! The point was to show you that at the end of the day, Linux does as Linux does, no matter what the distribution is or what kind of cpu architecture is running it. I learned things from my phone that became useful later while working with servers! Again, Linux does as Linux does; just find the inner shell, and you’re all set. Maybe you’ll only need to enable usb debugging on Android, or perhaps you’ll have to open up your Amazon Kindle and connect a serial port to a secret port, but in the end, you will feel as if you’re working with your own system, you’ll feel like home.

Notes:

1. well, actually 6 months ago when I drafted this post!
2. Do I really need to mention that I couldn’t enable any of those while in lockout? Give me some credit, man!
3. just to clarify: hacking equals curiosity, IMO.
4. aka. RTRM :-p I’m gonna start a “respect the manual” movement someday … ya’ll see …
5. I’ve just bought a Raspberry Pi and I did pretty much the same thing, in terminal! I’ll write about it soon

## John Nash’s Letter to the NSA

If you have watched A Beautiful Mind you probably remember John Nash, the genius mathematics professor at Princeton University. Recently a series of quite interesting letters from him to NSA has been declassified, although the letters might not be very interesting for many of you (plus, his handwriting is really bad!), but here is a short overview of the subject is you find it interesting.

Respectfully re-blogged from Noam Nisan’s post:

The National Security Agency (NSA) has recently declassified an amazing letter that John Nash sent to it in 1955.  It seems that around the year 1950 Nash tried to interest some US security organs (the NSA itself was only formally formed only in 1952) in an encryption machine of his design, but they did not seem to be interested.  It is not clear whether some of his material was lost, whether they ignored him as a theoretical professor, or — who knows — used some of his stuff but did not tell him.  In this hand-written letter sent by John Nash to the NSA in 1955, he tries to give a higher-level point of view supporting his design:

In this letter I make some remarks on a general principle relevant to enciphering in general and to my machine in particular.

He tries to make sure that he will be taken seriously:

I hope my handwriting, etc. do not give the impression I am just a crank or circle-squarer.  My position here is Assist. Prof. of Math.  My best known work is in game theory (reprint sent separately).

He then goes on to put forward an amazingly prescient analysis anticipating computational complexity theory as well as modern cryptography.  In the letter, Nash takes a step beyond Shannon’s information-theoretic formalization of cryptography (without mentioning it) and proposes that security of encryption be based on computational hardness — this is exactly the transformation to modern cryptography made two decades later by the rest of the world (at least publicly…).  He then goes on to explicitly focus on the distinction between polynomial time and exponential time computation, a crucial distinction which is the basis of computational complexity theory, but made only about a decade later by the rest of the world:

So a logical way to classify enciphering processes is by t he way in which the computation length for the computation of the key increases with increasing length of the key. This is at best exponential and at worst probably at most a relatively small power of r, $ar^2$ or $ar^3$, as in substitution ciphers.

He conjectures the security of a family of encryption schemes.  While not totally specific here, in today’s words he is probably conjecturing that almost all cipher functions (from some — not totally clear — class) are one-way:

Now my general conjecture is as follows: for almost all sufficiently complex types of enciphering, especially where the instructions given by different portions of the key interact complexly with each other in the determination of their ultimate effects on the enciphering, the mean key computation length increases exponentially with the length of the key, or in other words, the information content of the key.

He is very well aware of the importance of this “conjecture” and that it implies an end to the game played between code-designers and code-breakers throughout history.  Indeed, this is exactly the point of view of modern cryptography.

The significance of this general conjecture, assuming its truth, is easy to see.  It means that it is quite feasible to design ciphers that are effectively unbreakable.  As ciphers become more sophisticated the game of cipher breaking by skilled teams, etc., should become a thing of the past.

He is very well aware that this is a conjecture and that he cannot prove it.  Surprisingly, for a mathematician, he does not even expect it to be solved.  Even more surprisingly he seems quite comfortable designing his encryption system based on this unproven conjecture.  This is quite eerily what modern cryptography does to this day: conjecture that some problem is computationally hard; not expect anyone to prove it; and yet base their cryptography on this unproven assumption.

The nature of this conjecture is such that I cannot prove it, even for a special type of ciphers.  Nor do I expect it to be proven.

All in all, the letter anticipates computational complexity theory by a decade and modern cryptography by two decades.  Not bad for someone whose “best known work is in game theory”.  It is hard not to compare this letter to Goedel’s famous 1956 letter to von Neumann also anticipating complexity theory (but not cryptography).  That both Nash and Goedel passed through Princeton may imply that these ideas were somehow “in the air” there.

ht: this declassified letter seems to have been picked up by Ron Rivest who posted it on his course’s web-site, and was then blogged about (and G+ed) by Aaron Roth.

Edit: Ron Rivest has implemented Nash’s cryptosystem in Python.  I wonder whether modern cryptanalysis would be able to break it.

## The Genius Who Made it Simple

Dennis M. Ritchie

Today marks the passing of the pioneer of C and Unix, Dennis Ritchie, the R in K&R. I personally compare his innovation to language. Because both of them gave us the ability to communicate with another creature: humans, and computers. Without him and his partner, programming would be as hard as Electrical Engineering. He is a prophet among computer scientists 1.

Rest in Peace, Dennis Ritchie
1941 – 2011

// A farewell to Dennis Ritchie, in his own language
#include <stdio.h>

int main()
{
printf("Goodbye, World!\n");
return 0;
}

P.S: one of my favourite quotes about computers and specially Unix, is this: “UNIX is very simple, it just needs a genius to understand its simplicity.”. I believe in it, it’s so simple.

Notes:

1. if not a God, of course!

## Introduction to Systemd

Two weeks ago I was curious about how can I participate in Fedora project, and now, this is my first post on Planet Fedora! Yay! There are few ways to participate in fedora, like release engineering, packaging, infrastructure, documentation, etc., and I started with infrastructure!

The Infrastructure team consists of dedicated volunteers and professionals managing the servers, building the tools and utilities, and creating new applications to make Fedora development a smoother process. We’re located all over the globe and communicate primarily by IRC and e-mail.

In simple worlds, “We run the servers that run fedora!”. Currently I’m in fedora infrastructure apprentices group, with non-root access on many fedora servers around world, but the best part, is to be in a professional community

ok, that’s enough. This post is about systemd. Why am I interested in it? because I use fedora15 which is the first distribution with systemd feature enabled by default. First of all, what is systemd?

systemd is a system and service manager for Linux, compatible with SysV and LSB init scripts. systemd provides aggressive parallelization capabilities, uses socket and D-Bus activation for starting services, offers on-demand starting of daemons, keeps track of processes using Linux cgroups, supports snapshotting and restoring of the system state, maintains mount and automount points and implements an elaborate transactional dependency-based service control logic. It can work as a drop-in replacement for sysvinit. (From this presentation)

For myself, first time I saw it’s name it was in /etc/inittab file:

# inittab is no longer used when using systemd.
#
#
# Ctrl-Alt-Delete is handled by /etc/systemd/system/ctrl-alt-del.target
#
# systemd uses 'targets' instead of runlevels. By default, there are two main targets:
# multi-user.target: analogous to runlevel 3
# graphical.target: analogous to runlevel 5
#
# To set a default target, run:
# ln -s /lib/systemd/system/&amp;lt;target name&amp;gt;.target /etc/systemd/system/default.target

sysvinit looks the /etc/inittab file for runlevel and virtual console configurations, but in systemd, as you can see in the code above, we have targets and virtual consoles (ttys) are considered as services, just like other service and daemons. Each service is a file located in /lib/systemd/system or /etc/systemd/system. To get in touch with systemd, try systemctl and read systemd* manuals.

I think there are enough information and manuals on the net, like these, this or this, but one thing is missing in all of them … how to setup autologin on a virtual console with systemd? Here it comes as an example for systemd services:

### Autologin to virtual console terminals (tty) at startup

In sysvinit structure, setting autologin was as easy as editing one line of inittab file, but now we need to add a service, so we can have more control:

# cp /lib/systemd/system/getty@.service \
/etc/systemd/system/getty.target.wants/getty@tty8.service

then edit ExecStart, Restart and Alias values, like this:

...
Restart=no
...
Alias=getty.target.wants/getty@tty8.service

and then:

# systemctl daemon-reload
# systemctl start getty@tty8.service

Now press Ctrl-Alt-F8, and you should see the console waiting for you commands . Note that if you exit tty8 session, you wont be able to use it until next reboot or manual start by systemctl, except if you leave Restart as ‘always’, but I highly recommend to avoid this according to security reasons.

UPDATE: I was wondering what’s difference between /etc/systemd/system and /lib/systemd/system and hbt said “Everything in /lib is yum-territorium whereas /etc is admin-stuff”, so I’ve changed the commands above (autologin@.service moved from /lib to /etc, and getty@tty8.service must be updated).

## Project: HelliJudge

About two months ago Hamed Saleh and I have started a project to write a judge system named HelliJudge:

The system can compile and execute codes, and test them with pre-constructed data. Submitted code may be run with restrictions, including time limit, memory limit, security restriction and so on. The output of the code will be captured by the system, and compared with the standard output. The system will then return the result. (from Wikipedia)

In this project I faced many problems, and learned much more things like co-process, PAM, some NAT solutions, jailing (and some jailbreak techniques), many bash techniques, git and few other things.

Our system is based on the principle of least privilege. In simple words, we compile the code in a jailed environment with minimum needed libraries available for compiler, then run it in the same environment with hard limits on memory and number of threads with no write access — except for stdout and stderr. FYI, monitoring total time, memory and return code of user binary is what time does (note that gnu time is different from bash time, the gnu one only can be accessed with absolute path: /usr/bin/time).

The jailed area, which is available on its git repository, contains only gcc, gcc-c++, cpp, some needed libraries, bash and their requirements. Compile scripts (like this) are also included in the jail (actually this is the reason we need bash in the jailed zone).

Jail system used to be based on chroot, but for some issues we switched to pam_chroot (which is in PAM package in fedora). This module makes it easy to set a root directory for users and groups by editing /etc/security/chroot.conf. This is an example of the file:

# /etc/security/chroot.conf
# format:
#matthew        /home

judge        /mnt/jail

PAM is also used as limit system! We used pam_limits module to limit maximum thread count (in order to prevent fork bomb and zombie process attack) and limit maximum memory by editing /etc/security/limits.conf. Here is an example of the file:

# /etc/security/limits.conf
#
#Each line describes a limit for a user in the form:
#
#
#
#Where:
# can be:
#        - an user name
#        - a group name, with @group syntax
#        - the wildcard *, for default entry
#        - the wildcard %, can be also used with %group syntax,
#
# can have the two values:
#        - "soft" for enforcing the soft limits
#        - "hard" for enforcing hard limits
#
# can be one of the following:
#        - core - limits the core file size (KB)
#        - data - max data size (KB)
#        - fsize - maximum filesize (KB)
#        - memlock - max locked-in-memory address space (KB)
#        - nofile - max number of open files
#        - rss - max resident set size (KB)
#        - stack - max stack size (KB)
#        - cpu - max CPU time (MIN)
#        - nproc - max number of processes
#        - as - address space limit (KB)
#        - priority - the priority to run user process with
#        - locks - max number of file locks the user can hold
#        - sigpending - max number of pending signals
#        - msgqueue - max memory used by POSIX message queues (bytes)
#        - nice - max nice priority allowed to raise to values: [-20, 19]
#        - rtprio - max realtime priority
#
#
#

#*               soft    core            0
#@student        hard    nproc           20
#@faculty        soft    nproc           20
#@faculty        hard    nproc           50
#ftp             hard    nproc           0

judge            hard    core            0
judge            hard    nproc           1
judge            hard    as              524288

# End of file

We limited total time using timeout command.

In order to apply the limitations described below, we made a “judge” user, added him to chroot.conf and limits.conf (as you can see in the examples above, yes, they are really being used in our server), and then added these lines to /etc/pam.d/su:

session     required    pam_limits.so
session     required    pam_chroot.so

Note: the order of lines in PAM configuration files is important. pam_chroot.so should come at the end.

Now if you use “su” to run a command as user “judge”, these limits will be applied to session. For example the following command will run a.out with these limits (note that a.out is in root folder of jailed area):

# su judge --session-command /a.out

Currently just HelliCode (see the update) uses our system, which is actually another project of Mohammad Reza Maleki and us We would be glad if you test our system’s security at HelliCode.

P.S: As there isn’t much documentation available for co-processes, I’ll mention it asap.

UPDATE: Yay! A new server is going to use our judge! Algorithms.ir is a computer algorithm education and contest website by Mr. Andjedani in Algorithms and Problem Solving Laboratory in Department of Computer Science at Sharif University of Technology.

## To Kill or Not to Kill, this is the answer!

Kill! Is it just a command to terminate a process? I don’t think so … . Actually the word “kill” is a real misnomer for this command, as it’s main job is to send signals to processes. then, what the hell is signal?

A signal is a limited form of inter-process communication used in Unix, Unix-like, and other POSIX-compliant operating systems. Essentially it is an asynchronous notification sent to a process in order to notify it of an event that occurred. [...] If the process has previously registered a signal handler, that routine is executed. Otherwise the default signal handler is executed. (from Wikipedia)

I’m going to mention few things about the kill command and few useful signals in this post.

#### KILL

In POSIX-compliant operating systems (such as Linux, *BSD, Solaris, etc.) kill command is used to send a signal to one or more processes. If no signal is specified in command line, the default signal is send, which is SIGTERM. This signal terminates the process but it can do some backup operations such as saving log or writing final changes to an open file, according to the signal handler in the process; If no handler is specified, then the default routine will be executed and the process terminates.
Note added later: Did you ever seen a process that you want to terminate it, but it doesn’t? Maybe the process has a kind of signal handler that is taking time to finish. You can force it using SIGQUIT.

But this was only one of 64 signals available (at least on my system! I’m sure that not all Unix-based operating systems are as same as mine!). Let’s take a look at list of signals:

[mahrud@eve ~]$kill -l 1) SIGHUP 2) SIGINT 3) SIGQUIT 4) SIGILL 5) SIGTRAP 6) SIGABRT 7) SIGBUS 8‌) SIGFPE 9) SIGKILL 10) SIGUSR1 11) SIGSEGV 12) SIGUSR2 13) SIGPIPE 14) SIGALRM 15) SIGTERM 16) SIGSTKFLT 17) SIGCHLD 18) SIGCONT 19) SIGSTOP 20) SIGTSTP 21) SIGTTIN 22) SIGTTOU 23) SIGURG 24) SIGXCPU 25) SIGXFSZ 26) SIGVTALRM 27) SIGPROF 28) SIGWINCH 29) SIGIO 30) SIGPWR 31) SIGSYS 34) SIGRTMIN 35) SIGRTMIN+1 36) SIGRTMIN+2 37) SIGRTMIN+3 38) SIGRTMIN+4 39) SIGRTMIN+5 40) SIGRTMIN+6 41) SIGRTMIN+7 42) SIGRTMIN+8 43) SIGRTMIN+9 44) SIGRTMIN+10 45) SIGRTMIN+11 46) SIGRTMIN+12 47) SIGRTMIN+13 48) SIGRTMIN+14 49) SIGRTMIN+15 50) SIGRTMAX-14 51) SIGRTMAX-13 52) SIGRTMAX-12 53) SIGRTMAX-11 54) SIGRTMAX-10 55) SIGRTMAX-9 56) SIGRTMAX-8 57) SIGRTMAX-7 58) SIGRTMAX-6 59) SIGRTMAX-5 60) SIGRTMAX-4 61) SIGRTMAX-3 62) SIGRTMAX-2 63) SIGRTMAX-1 64) SIGRTMAX Note: I’m sure that there is enough information on each of them at Linux manuals, etc. so RTFM . But there are few useful signals in which I’m interested: • SIGSTOP + SIGCONT: It had happened many times for me that a heavy/buggy process slows down the system, but I don’t want to interrupt it; These two signals are used to stop a process’s job and then continue it. • SIGQUIT: This signal is useful when you want to interrupt the process immediately and to dump memory state, aka core dump (I’m interested in how to use ‘core dumps’ in debugging, etc., just leave it for later!) Note added later: This signal can be manually sent using ^\ short key (^ means Ctrl! So ^\ is equal to Ctrl + \) • Information Signals: Signals such as: SIGALRM, SIGIO (SIGPOLL for Linux), SIGTTIN, SIGTTOU, SIGURG (at least I think) are used to inform the process about a non-fatal event. • Error Signals: Signals such as: SIGHUP, SIGILL, SIGTRAP, SIGBUS, SIGFPE, SIGSEGV, SIGXCPU, SIGXFSZ, SIGPWR, SIGSYS are all used to terminate the process in case of a fatal error, like Floating Point Exception (SIGFPE), Segmentation Violation (SIGSEGV), Power Failure (SIGPWR), etc. . look at this example for SIGFPE: (there are two terminals, and 7547 is PID of a.out) [mahrud@eve ~]$ kill -s SIGFPE 7547
[mahrud@eve C-CPP]$./a.out Floating point exception (core dumped) [mahrud@eve C-CPP]$ 
• Reserved Signals: SIGUSR1 and SIGUSR2 are reserved for programmers in order to call/indicate a user-defined routine/event in their program. This is a good idea to communicate between threads of a process or dependent processes (Look at this for few examples of these user-defined signal handlers).

WOW! Isn’t it great?! Linux kernel (or in general, a Unix-based kernel) is a wonderful and dreamy code that you can do anything in it! I love it!

I’m working on using signal handlers in C++.