Category Archives: Academics

File encryption and decryption using symmetric key

Symmetric-key encryption is the type of encryption where the key used to encrypt and decrypt a file is the same. Symmetric  key encryption can use two types of ciphers :

  1. Block Ciphers : Here, the message to be sent, is divided into blocks of fixed size and each block is encrypted using the same key. Thus similar blocks when encrypted using the same key give the same output (AES – Advanced Encryption Standard has 128 bits in a block).
  2. Stream Ciphers : In this cipher, each bit of the message to be encrypted, is encrypted separately.

Encrypting and decrypting a file using symmetric key :

Put the text to be encrypted into a file. Let the contents of the file to encrypted  be :
This is a secret.
The name of the file to be encrypted is secret.

savita@Amrita:~/secure_os$ gpg --symmetric secret

A password is prompted for, which is the key. A file called secret.gpg gets formed. This is the encrypted file. You can view the contents of the file.

savita@Amrita:~/secure_os$ cat secret.gpg
�vu�ƿѥ`�-Y���������V�|�*l5#` ��vf1#ah��v������8�

Now if you want to decrypt the file, run the following command :

savita@Amrita:~/secure_os$ gpg --decrypt secret.gpg

and enter the correct password. You get the following output which contains the text that you encrypted.

gpg: CAST5 encrypted data
gpg: encrypted with 1 passphrase
This is a secret. gpg: WARNING: message was not integrity protected

Bingo! You just encrypted and decrypted a file using a symmetric key. This uses the CAST5 algorithm for encryption.

Advertisements

Verify the signature of Linux kernel

When you download Linux kernel (or for that matter any file such as an Ubuntu image), there are high chances that the file may be corrupted. In order to verify that the file is not corrupted is coming from the right source (that is, comes from the person making the release), a signature of the person making the release is provided along with each release. This sign can then be verified to find out if the files have been tampered with. Public key cryptography is used for signing and verification and it is next to impossible to forge the signature (unless of course the person trying to forge, has the private key of the victim whose signature he is trying to forge). The sign can be verified using GnuPG. All you have to do is :

1. Download the linux kernel and the corresponding sign from the person making the release.

savita@Amrita:~$ wget https://www.kernel.org/pub/linux/kernel/v3.0/linux-3.1.5.tar.xz

2. Download the corresponding sign for the kernel release.

savita@Amrita:~$ wget https://www.kernel.org/pub/linux/kernel/v3.0/linux-3.1.5.tar.sign

3. Unzip the linux kernel.

savita@Amrita:~$ unxz linux-3.1.5.tar.xz

4. Verify the sign.

You will probably get the following output.

gpg: Signature made Fri 09 December 2011 10:46:46 PM EST using RSA key ID 6092693E
gpg: Can't check signature: public key not found

This is because you need to download the public key from PGP server to check the sign.

5. Now download the public key from the PGP server. We get the key ID from above.

savita@Amrita:~$ gpg --recv-keys 6092693E
gpg: requesting key 6092693E from hkp server keys.gnupg.net
gpg: key 6092693E: public key "Greg Kroah-Hartman (Linux kernel stable release signing key) <greg@kroah.com>" imported
gpg: 3 marginal(s) needed, 1 complete(s) needed, PGP trust model
gpg: depth: 0  valid:   4  signed:   0  trust: 0-, 0q, 0n, 0m, 0f, 4u
gpg: Total number processed: 1
gpg:               imported: 1  (RSA: 1)

6. Verify again using GnuPG.

savita@Amrita:~$ gpg --verify linux-3.1.5.tar.sign

You will get this :

gpg: Signature made Friday 09 December 2011 10:46:46 PM IST using RSA key ID 6092693E
gpg: Good signature from "Greg Kroah-Hartman (Linux kernel stable release signing key) <greg@kroah.com>"
gpg: WARNING: This key is not certified with a trusted signature!
gpg:          There is no indication that the signature belongs to the owner.
Primary key fingerprint: 647F 2865 4894 E3BD 4571  99BE 38DB BDC8 6092 693E

The “Good”  signature shows that the file has not been tampered with. There are also chances of the signature being “Bad”. This may be due to the fact that the file is corrupted, or it was not downloaded completely. But there is a warning. You still need to verify whether the sign used, still belongs to the person who made the release, that is, in this case, George Kroah-Hartman. This can be done in two ways. Either follow the Web Of Trust used in PGP or go through the list of people who have signed the person’s key (using the command gpg gpg --list-sigs) and contact them to check if they really signed it and someone else did not fake it. You can thereby verify that the signature on the Linux kernel is genuine.

Reference : http://www.kernel.org/signature.html

Gpg key pair generation

A week ago, I learnt how to create a key pair (public key and private key) using gpg. I thought I’d blog about it. This blog post is a tutorial on how to do exactly that. It is extremely simple.

All that you have to do is to open up a terminal and run the command :

savita@Amrita:~$ gpg --gen-key
savita@Amrita:~$ gpg --gen-key
 gpg (GnuPG) 1.4.11; Copyright (C) 2010 Free Software Foundation, Inc.
 This is free software: you are free to change and redistribute it.
 There is NO WARRANTY, to the extent permitted by law.

Please select what kind of key you want:
 (1) RSA and RSA (default)
 (2) DSA and Elgamal
 (3) DSA (sign only)
 (4) RSA (sign only)
 Your selection?
 RSA keys may be between 1024 and 4096 bits long.
 What keysize do you want? (2048)
 Requested keysize is 2048 bits
 Please specify how long the key should be valid.
 0 = key does not expire
 <n>  = key expires in n days
 <n>w = key expires in n weeks
 <n>m = key expires in n months
 <n>y = key expires in n years
 Key is valid for? (0)
 Key does not expire at all
 Is this correct? (y/N) y

You need a user ID to identify your key; the software constructs the user ID
 from the Real Name, Comment and Email Address in this form:
 "Heinrich Heine (Der Dichter) <heinrichh@duesseldorf.de>"

Real name:
 Real name: Savita TS
 Email address: savita.seetaraman5@gmail.com
 Comment: Gpg Key-Pair Generation
 You selected this USER-ID:
 "Savita TS (Gpg Key-Pair Generation) <savita.ts@gmail.com>"

Change (N)ame, (C)omment, (E)mail or (O)kay/(Q)uit? o
 You need a Passphrase to protect your secret key.

You now get a pop up asking you to enter the pass phrase. Enter a secure pass.


We need to generate a lot of random bytes. It is a good idea to perform
 some other action (type on the keyboard, move the mouse, utilize the
 disks) during the prime generation; this gives the random number
 generator a better chance to gain enough entropy.

Not enough random bytes available.  Please do some other work to give
 the OS a chance to collect more entropy! (Need 118 more bytes)
 .+++++
 .....+++++
 We need to generate a lot of random bytes. It is a good idea to perform
 some other action (type on the keyboard, move the mouse, utilize the
 disks) during the prime generation; this gives the random number
 generator a better chance to gain enough entropy.
 ..+++++
 +++++
 gpg: key 3D4F13E9 marked as ultimately trusted
 public and secret key created and signed.

gpg: checking the trustdb
 gpg: 3 marginal(s) needed, 1 complete(s) needed, PGP trust model
 gpg: depth: 0  valid:   4  signed:   0  trust: 0-, 0q, 0n, 0m, 0f, 4u
 pub   2048R/3D4F13E9 2013-01-17
 Key fingerprint = 7DEF 17A4 D20B E290 BF7D  6D33 D7ED 37EF 3D4F 13E9
 uid                  Savita TS (Gpg Key-Pair Generation) <savita.ts@gmail.com>
 sub   2048R/9646B948 2013-01-17
 

Bingo! You’ve just created your public key. Now you need to export the key. 😀

Exporting the key :


savita@Amrita:~$ gpg --export savita > public_key.gpg

If you open and see this file, you see gibberish. If you want to see the key in ascii format, then all you have to do is to execute the following command. You have to add one more argument, –armor along with it.


savita@Amrita:~$ gpg --armor --export savita > public_key_ascii.gpg

Importing others’ key

If you want to import other people’s public key, this is what you have to do :

savita@Amrita:~$ gpg --import <filename>

where filename is the name of the file that contains the key.
Now we get to the encryption and decryption part.

Encrypting a file using the public key :

You can now encrypt your files using the public key that you just created. If you want to send a message to xyz you first encrypt message (which is a file containing the message that you want to deliver), this is what you do  :

savita@Amrita:~$ gpg --recipient xyz --encrypt message

Decrypting a file using the public key :

Suppose that you receive a message that has been encrypted with the public key of the sender (imagine yourself in the shoes of xyz who has just received the message that you sent earlier) and you want to decrypt it. You do so using your private key. You need to do the following :

savita@Amrita:~$ gpg --decrypt message.asc

The .asc denotes that the contents of the file is in ASCII format. You will now be asked for the passphrase.

savita@Amrita:~$ gpg --decrypt message.asc
You need a passphrase to unlock the secret key for user: "savita (Gpg Key-Pair Generation) "
2048-bit ELG-E key, ID 35C5BCDB, created 2010-01-02 (main key ID 90130E51)

References :
This site helped me out a lot. But for this site, I would not have been able to complete this assignment.

Internal and External Linux commands

Linux commands can be classified into two categories :

  1. External
  2. Internal

Let’s look into what External Linux commands are.

External commands programs with files in /bin directory (In Linux, everything is represented in the form of files). If the files are not present in the path specified by the $PATH variable, they do not get executed. Similarly, if the files are available but are not present int the path specified by $PATH, the commands cannot be executed. Another point worth noting is that every time an external command gets executed, a new process gets spawned.

Internal commands are those which are directly executed by the shell. These are built-ins in the shell. They do not depend on paths since they are not coded in files. Unlike external commands no process is created when an internal command is executed.

How to distinguish between internal and external commands ?

There is a Linux command type, which (quoting the Wikipedia) specifies how its arguments would be interpreted if they were used as a command name. This command could be used to identify between the two types of commands. Execute the command : type <command>

If the output states that the command is shell built-in, it is an internal command. Instead, if the output states that the command is present in /bin, then it is an external command.

For example, cd and pwd are examples of internal commands.


savita@Amrita:~$ type cd
cd is a shell builtin
savita@Amrita:~$ type pwd
pwd is a shell builtin
savita@Amrita:~$

cp and mv are examples of external commands.


savita@Amrita:~$ type cp
cp is /bin/cp
savita@Amrita:~$ type mv
mv is /bin/mv
savita@Amrita:~$

However, there might be certain commands which have files in /bin directory and at the same time, are also built-ins in the shell. In such cases, the first preference would always be given to the internal command, meaning that, even if the corresponding file did not exist, it would be executed by the shell as a built-in. One example is the Linux command echo.

Differences between the two types of commands :

Summarizing the above two paragraphs, some of the differences between internal and external commands (from what I understood about them) are :

External Linux Commands

Internal Linux Commands

These are executed by the kernel. These are executed by the shell.
A separate process is spawned every time a new external command is executed. No new process is created.
These are separate files in /bin directory. The execution of these commands happens through the execution of their corresponding files in /bin directory. These are built-ins in the shell. The execution of these commands happens through the execution of their corresponding files in /bin directory.
A few examples are cp, mv, etc. Some examples are cd, pwd, etc.

References : 1   2

Semaphores

A Semaphore is a variable type that provides good abstraction for the process of controlling the access to a resource by many processes in a multiprogramming environment. It can be understood as a simple variable that keeps account of the number of resources that are available, or to be more precise, how many units of a particular resource are available.The semaphores cannot be accessed directly. The kernel itself provides the protection for semaphores.The Operating textbook written by Silberschatz and Galvin beautifully explains what a semaphore is.

Semaphores are of two types :

a. Binary Semaphores : The only values possible are 0 and 1. They have the same functionality as that of mutexes.

b. Counting Semaphores : Any arbitrary number is possible. They are used to allow controlled access to a particular resource. If the count is greater than zero, there are resources available, which can be used by the processes. If the count is less than zero, then it means that no resources are available for use.

More specifically , a semaphore can be considered as a data type that has an integer value as well as a process list. The integer keeps track of the number of resources that are available whereas the list maintains a list of processes that have not been given the required resources. If a process has not been allocated the necessary resources, it is put in the waiting queue for that particular resource, maintained by the semaphore that deals with the controlled access of the resource under consideration.

The definition for a semaphore data type is as follows :

struct sem {
    int count;
    Queue process;
};

The two operations that are performed by the semaphores are :
1. Wait ()
2. Signal ()

The value of a semaphore cannot be changed in any other method than by calling wait and signal.

1. Wait() (also known as Operation P – Proberen)
2. Signal() (also known as Operation V – Verhogen)

The code for P operation is as follows :

void wait(sem s) {
    s.count--;
    if (s.count < 0) {
        /*Place the process in the waiting list  (s.queue)*/
        /*block this process */
    }
}

The code for V operation is as follows :

void signal(sem s) {
    s.count++;
    if (s.count <= 0) {
        /*remove the process from the P from the s.queue;
        /*place the process in the ready queue*/
    }
}

Functioning of a Semaphore :

The P operation sleeps till the resource guarded by he semaphore is available. The V operation increments the number of resources available when an operation is executed and the resources have been finished using. If suppose the value of a semaphore was initially 1. When a process requests for a resource, the wait() system call is performed on the semaphore and its value is decreased by one. The current value of the semaphore is zero. Now the next time that another process requests for the resource, it is is not available and thus the process is put into the list of processes maintained by the semaphore.
Now if suppose the first process has completed using the resource and is now ready to release it. In such a case, it calls a signal() on the semaphore which increments the value of the count. The resource now becomes available again for use by other processes. At this time, one among all those processes that were waiting for the resource is freed from the list of processed maintained by the process and it is placed in the ready queue.

Point to be Noted :
Under the classical definition of a semaphore the count value never becomes negative. That is because initially, busy waiting was the technique used to implement the semaphore. But after noticing that busy waiting only wasted a lot of CPU cycles that could be used by other processes efficiently, the concept of including a list of processes which are waiting for a resource to be allocated to them, was introduced.

Classical problems of Process Synchronisation in Operating Systems

Synchronization between processes is of great importance as far consistency of data is considered.

There are a few classical problems regarding synchronization, that have been commonly discussed over the past few years. These problems are very much similar to the problems that are faced in real by Operating Systems in making sure that every process has the required number of resources. Some of these problems are:

  • Producer Consumer Problem
  • Reader Writer Problem
    • giving preference to the readers
    • giving preference to the writers
  • Dining Philosophers’ Problem
  • Sleeping Barber Problem

Various possible solutions have been discussed for each problem, each solution of which can be worked out in different methods. Some of the different approaches are :

  • Using counter
  • Using Semaphores
  • Using Monitors

Each approach has got its own pros and cons.

The next post will be about Producer Consumer Problem and how to solve it using a counter and semaphores. Monitors will be explained later.

Some common terms related to Process Synchronisation

Process Synchronization is very important to an Operating System where data consistency is concerned. Some of the common terms related to Process Synchronization are as follows :

Critical Section : This is a part of the code which accesses shared resources and it is required that the critical section should not be executed when there are than one processes for the scheduler to choose from.

Atomic Operation : There may be some set of instructions that may have to be executed together. They are indivisible. No one can view the intermediate the status of the operations neither can anyone interrupt them.

Mutual Exclusion : When one process is accessing the critical section that edits a global data no other process should access a critical region that changes the shared resource.

Deadlock : A deadlock is a condition where one process is waiting for a resource to be released by another process which is itself waiting for another process to be released by the current process. Unlike other problems faced by the Operating Systems, this problem is permanent and there is no solution to it.

Race Condition : This is the condition in which multiple threads or processes can access and edit the data in the critical region and the value of the resource depends on the order of relative speed of execution of the threads.

Starvation : A starved process is one which is overlooked by the scheduler. Although it is ready to execute it is not provided with the resources that it requires, for various reasons.

Some of the problems faced during concurrency :

  • Sharing global resources : When two processed access the same variable depends upon the order of usage of the two processes. It depends upon the order in which they access the critical region.
  • Request for resources : When process requests for a particular resource and then enters the wait state, other processes will not be able to access that resource. This may even lead to deadlock.