avatar tianjara.net | blog icon Andrew Harvey's Blog

Entries from July 2010.

Operating Systems Notes
31st July 2010

Here are are some rough notes I put together as part of revision for a uni course. They are heavily based on the course lecture notes by Kevin Elphinstone and Leonid Ryzhyk. All diagrams are sourced from those lecture notes, some of which are in turn from the text book, A. Tannenbaum, Modern Operating Systems.

OS Overview

System Calls

Processes and Threads

During the system initialisation background processes (called daemon's on linux, service's on windows) and foreground processes can be started.

Threads Implementation



File Systems

There are many popular file systems in use today. FAT16, FAT32 are good for embedded devices; Ext2, Ext3, Ext4 are designed for magnetic disks, ISO9660 is designed for CD-ROM's, JFFS2 is optimised for flash memory as you don't want to write to the same location too many times as it wears out. Others include NTFS, ReiserFS, XFS, HFS+, UFS2, ZFS, JFS, OCFS, Btrfs, ExFAT, UBIFS.

Performance issues with standard magnetic disks

Block Allocation Strategies

External fragmentation - space wasted external to the allocated regions, this space becomes unusable as its not contiguous (so you have lots of small spaces but you need a larger space to fit a whole file in)

Internal fragmentation - space wasted internal to the allocated memory regions, eg. you get a 4K block allocated and only use 1K, but the OS can't give the leftover 3K to someone else.

Keeping track of file blocks

System call interface

File syscall interface


Journaling file system keeps a journal (or log) of FS actions which allows for the FS to recover if it was interrupted when performing an action that is not atomic, but needs to be.

Memory Management and Virtual Memory

Virtual Memory

Input Output



Multiprocessor Systems


Tags: computing.
Security Engineering Notes
31st July 2010

Here are are some rough notes I put together as part of revision for a uni course.

Security Engineering


Extra notes from Schinder 2nd Ed.


Choose two primes p and q and let n = pq. Choose e such that e and (p - 1)(q - 1) are relatively prime (ie. no common factor and both prime numbers). Let d be a solution of ed = 1 mod (p-1)(q-1). Public key $latex K = (e,n)$, private key $latex K^{-1} = (d,n)$.

$latex E_K(M) = M^e \mod n$

$latex D(M) = E_{K^-1}(M) = M^d \mod n$

Access Control


You want your elections to be,

(additional notes, but don't really need to know for exam)

Security Architecture

Security Design Principles:

Defence in depth - use many layers of security (or many security perimeters in layers)

Human Factors

Some strategies for reducing the risk,


Risk is not something I would have thought to be in a security course, but now that I think about it there are few if any bullet proof systems, so there is always some risk.

Whether it be secure communication (there is always some risk that an eavesdropper cracks your cryto and reads the message, so its important to weigh up those risks to decide if its worth sending the message in the first place), or be it running a web server (you cannot be sure that your web server doesn't have bugs, or even if you have verified the code to be matching the vulnerability free specification other things can happen like, has your CPU been verified to be bug free, are you sure that a cosmic ray won't flip a bit and subsequently create a vulnerability). So weighing up the risks involved is important to decide how much time and effort you devote to securing a system, or how the system is designed to work.

Business Risk Concepts

Degree of Risk

       <-- Probability -->
High Exposure/  |  High Exposure/         /\
Low Probability |  High Probability       ||
-----------------------------------    Exposure
Low Exposure/   |  Low Exposure/          ||
Low Probability |  High Probability       \/

Exposure - how widespread is the system? Probability - how easy is it to exploit the system, and how great is the incentive to do so (which relates to how valuable the assets you are protecting are)?

Risk management

Tags: computing.
A Great Gnome Panel Applet + A UPnP Enabled Router
26th July 2010

I have just discovered that my ADSL router supports UPnP, and that this provides an interface to access 3 important bits of information from the router (external IP address, total bytes sent and total bytes received). I had previously been scraping the router's web interface to grab the external IP. As for the bytes sent and received, I didn't even know the router had a method of reporting these.

My first instinct was to look for a Perl library for UPnP, I found two. One in the Ubuntu repositories (and in CPAN) http://search.cpan.org/perldoc?Net::UPnP::GW::Gateway and another which appears to be in neither, http://perlupnp.sourceforge.net/.

I tried out the first one and after some fiddling get it working (though I haven't yet been able to eliminate the 2 seconds it spends blocked, ie. not executing on the CPU but still not complete).

Next I found a great program that allows you to place an arbitrary command's output in the Gnome Panel, http://code.google.com/p/compa/. Which resulted in,

Compa Gnome panel applet showing total bytes recieved and sent by the router.

The Perl script I use to provide the output to the Compa applet is at http://github.com/andrewharvey/perlmisc/blob/master/upnp_router_inoutbytes_to_compa.pl

Tags: computing, dev.
A method for two parties to verify if they share a common secret without revealing that secret if they don't.
23rd July 2010

We didn't cover zero knowledge proofs in the Security Engineering course I did last semester. But part way into the course I needed a way for two people, A and B to verify that some number they each know is infact the same number N in the case that they don't have a trusted arbitrator and they don't want to reveal the number they each know to the other person unless the other person has the same number.

I don't think this is exactly a zero knowledge proof situation by it seems closely related. The motivating situation for this was a web application that set some cookies and I wanted to know if one of these cookies set was unique per user or unique per some other setting (but the web application doesn't allow just anyone to create a new account, so I couldn't determine this on my own). In the case that it was unique per user then I don't want to tell anyone what my value for this cookie is because then they may be able to hijack my session.

So a method I thought of was that each person reveals one bit of the number to the other person at a time.

I'll try to formalise this a bit more.

I'll call this number the message. $latex A_M$ is the message $latex A$ knows, $latex B_M$ is the message $latex B$ knows. $latex A$ and $latex B$ arrange that they each know some message and arrange that they wish to verify if $latex A_M = B_M$. If $latex A_M = B_M$ then $latex A$ and $latex B$ must each know that that is the case and if $latex A_M \ne B_M$ then $latex A$ and $latex B$ must also know (after conducting the verification) that this is the case, but do not wish to let the other one know what their message was.

$latex A$ and $latex B$ meet letting $latex A$ be the entity that begins the verification. Each message is first encoded into a binary representation using an agreed upon method. $latex A$ then tells $latex B$ what the 1st bit of $latex A_M$ is (denoted $latex A_M \left [1\right ]$). $latex B$ now verifies this bit with $latex B_M$. If $latex A_M \left [1\right ] = B_M \left [1\right ]$, $latex B$ tells $latex A$ the second bit of $latex B_M$. If $latex A_M \left [1\right ] \ne B_M \left [1\right ]$, $latex B$ randomly selects a bit (ie. randomly selects either 0 or 1) and tells $latex A$ that random bit instead, and flags that $latex A_M \ne B_M$. As soon as either $latex A$ or $latex B$ flags that $latex A_M \ne B_M$ they subsequently always report a random bit regardless of whether the last bit reported to them was correct or not.

We could use an end of message token to indicate the end of the message. Of course this method isn't perfect because if one's random stream of bits matches what the other expects then one thinks that $latex A_M = B_M$ but the other thinks that $latex A_M \ne B_M$.

Another problem is if both parties have determined that $latex A_M \ne B_M$ then when do they stop sending random bits to each other? If both parties are happy to reveal the length of their message then there is no problem. Otherwise both parties can keep sending random bits until they feel that the the message space they have opened up is large enough and they don't mind revealing that the length of their message is less than the bit number they are up too.

Here's an example. A's number is 0110. B's number is 0110 and they want to check if they share the same number.

A -> B: 0 (B expects this)
B -> A: 1 (A expects this)
A -> B: 1 (B expects this)
B -> A: 0 (A expects this)
A -> B: $ (B expects this) (not needed if they first agree on revealing the message length)

Another case A knows 0110, B knows 0010.

A -> B: 0 (B expects this)
B -> A: 0 (A does not expect this, so A concludes A_M != B_M, and subsequently sends randomness)
A -> B: Rand(0,1) (two cases)
    A sent 0 (B does not expect this, so B also concludes A_M != B_M, and subsequently sends randomness)
        ... continues until the end of M or until one party stops sending randomness.
    A sent 1 (B expects this, but A hasn't revealed anything as they made a random selection)
        B -> A: 0 (A doesn't know if B is sending randomness or not)
        if they agreed upon a message length,
            (A knows that A_M != B_M, but B thinks that A_M == B_M)
            (but A has only revealed 1 bit of A_M to B (because B doesn't know if A was sending A_M or randomness after the 1st bit),
             and B hasn't revealed anything of B_M to A (because A doesn't know if B was sending randomness))#
            (the probability of this happening is z)
        or, no message length agreed upon,
            A keeps sending randomness and B will detect this (because B is expecting the end of stream token and didn't get it), so they both know that A_M != B_M.

This is not very formal and I'm confident I've missed some details or left some a bit fuzzy, I only really wanted to explain the general concept.

To be honest I'm not so sure if this is correct. Rather than me going around in circles unable to solve the math, and just abandoning this post, I'll just leave it be and post with this uncertainty.

Tags: mathematics.

RSS Feed