## Twinkle twinkle little star

Twinkle twinkle little star is a short musical piece I composed and recorded last evening.

This piece consists of 56 measures. It is 1 minute 52 seconds long. The music is composed of four tracks. This is my second attempt at recording music with multiple tracks. The last such attempt was more than two years ago when I composed and recorded 'A few notes'.

The links to the audio files, sheet music, etc. are provided below. The files reside in my website. In case, my website is down, the YouTube link provided below should still work.

The four tracks in this piece are:

1. Grand piano
2. Slow strings
4. Music box

This arrangement is based on the popular melody of the nursery rhyme called Twinkle, twinkle, little star. The melody is played with the treble notes of the piano. I wrote the bass notes for the piano and the strings, and the high notes for the pad and the music box to fill the music with emotions of love and happiness. I recorded this after about two hours of practice.

[music]

## AUTH CRAM-MD5

I was playing with a few SMTP authentication mechanisms while setting up my SMTP server. I found CRAM-MD5 authentication mechanism particularly interesting as it is a challenge-response authentication mechanism and involves HMAC-MD5. Let me first show a complete session with an SMTP server before coming to CRAM-MD5. Note that I am not using TLS or SSL in the sessions displayed below so that the SMTP traffic can be seen as plaintext. In practice, any email program should be configured to use TLS or SSL while having a session with an SMTP server. In the following session, I have selected the PLAIN authentication mechanism.

susam@nifty:~\$ telnet susam.in 25
Trying 106.187.41.241...
Connected to susam.in.
Escape character is '^]'.
220 tesseract.susam.in ESMTP Exim 4.72 Mon, 07 Nov 2011 20:27:56 +0530
EHLO nifty.localdomain
250-tesseract.susam.in Hello nifty.localdomain [122.167.80.194]
250-SIZE 52428800
250-PIPELINING
250-STARTTLS
250 HELP
AUTH PLAIN AGFsaWNlAHdvbmRlcmxhbmQ=
235 Authentication succeeded
MAIL FROM:<alice@susam.in>
250 OK
RCPT TO:<example.recipient@gmail.com>
250 Accepted
DATA
354 Enter message, ending with "." on a line by itself
Date: Mon, 07 Nov 2011 20:28:00 +0530
From: Alice <alice@susam.in>
To: Example Recipient <example.recipient@gmail.com>
Subject: Test email

This is a test email.
.
250 OK id=1RNQef-0004e7-7s
QUIT
221 tesseract.susam.in closing connection
Connection closed by foreign host.


In the AUTH PLAIN line I have sent the base64 encoding of the string \0alice\0wonderland. \0 indicates a null character, alice is the sender's user name and wonderland is the sender's password. If an eavesdropper intercepts this network traffic, he can easily find the user's password by simply decoding the base64 response sent by the client. This is also susceptible to replay attacks as the eavesdropper can use the AUTH PLAIN line containing the base64 encoded credentials to log into the server in future. This is why it is very important to secure the connection with TLS or SSL while having a session with the SMTP server.

Now, let me quickly show only the relevant lines for an authentication using the LOGIN mechanism.

AUTH LOGIN
334 VXNlcm5hbWU6
YWxpY2U=
334 UGFzc3dvcmQ6
d29uZGVybGFuZA==
235 Authentication succeeded


What is happening here becomes clear by decoding the base64 encoded messages. The following statements in Python 2.7.2 decode these messages.

>>> 'VXNlcm5hbWU6'.decode('base64')
>>> 'YWxpY2U='.decode('base64')
'alice'
>>> 'UGFzc3dvcmQ6'.decode('base64')
>>> 'd29uZGVybGFuZA=='.decode('base64')
'wonderland'


If the session isn't encrypted, LOGIN authentication mechanism is susceptible to the same problems that PLAIN authentication mechanism is susceptible to. Now, let me describe the CRAM-MD5 authentication mechanism. When the client selects the CRAM-MD5 authentication mechanism, the server sends a base64 encoded challenge as shown below.

AUTH CRAM-MD5


An HMAC is calculated for this challenge with the password as the key and MD5 as the hash function. A string is formed by concatenating the user name, a space and the hexadecimal representation of the HMAC. The base64 encoding of this string is sent as the response by the client. The following statements I tried in Python 2.7.2 show how a response can be formed for the above challenge.

>>> 'PDE3ODkzLjEzMjA2NzkxMjNAdGVzc2VyYWN0LnN1c2FtLmluPg=='.decode('base64')
'<17893.1320679123@tesseract.susam.in>'
>>> import hmac, hashlib
>>> hmac.new('wonderland', '<17893.1320679123@tesseract.susam.in>', hashlib.md5).hexdigest()
'64b2a43c1f6ed6806a980914e23e75f0'
>>> 'alice 64b2a43c1f6ed6806a980914e23e75f0'.encode('base64')
'YWxpY2UgNjRiMmE0M2MxZjZlZDY4MDZhOTgwOTE0ZTIzZTc1ZjA=\n'


Of course, this can be written as a small function:

import hmac, hashlib
return (username + ' ' +
base64challenge.decode('base64'),
hashlib.md5).hexdigest()).encode('base64')


The following snippet shows the SMTP server accepting the client-response.

AUTH CRAM-MD5
YWxpY2UgNjRiMmE0M2MxZjZlZDY4MDZhOTgwOTE0ZTIzZTc1ZjA=
235 Authentication succeeded


CRAM-MD5 authentication mechanism is relatively more secure than the other two mechanisms even if the connection is not secured because the password cannot be retrieved by decoding the base64 encoded client-response. The password is used as the key to calculate the HMAC but the password is not present anywhere in the response. It prevents replay attacks too because the server sends an unpredictable challenge for every authentication. The client-response computed for a certain challenge is invalid for further authentications which will involve different unpredictable challenges.

1. RFC 4954: SMTP Service Extension for Authentication
2. RFC 4616: The PLAIN Simple Authentication and Security Layer (SASL) Mechanism
3. RFC 2195: IMAP/POP AUTHorize Extension for Simple Challenge/Response
4. RFC 2104: HMAC: Keyed-Hashing for Message Authentication

## When worse is better

Let me begin this post with a puzzle.

Alex and Bob worked as financial advisers for the same company. They drew equal salaries from the company. They behaved well at the office. Both worked on similar assignments. Each assignment required a yes-no decision. The company used the decisions made by them to make profits.

After the recession hit the company very badly, they have to fire one of them. Both Alex and Bob have worked on almost the same number of assignments in the last ten years. Alex has been consistently taking about 80% decisions correctly every year. Bob, on the other hand, has been taking only about 5% correct decisions every year.

The company has decided to keep Bob and fire Alex. Why?

If you want to solve this puzzle yourself, you might want to stop here and think for a while. There are spoilers ahead.

Before giving away the solution to this puzzle, let me discuss something else.

Shannon's noisy channel coding theorem guarantees that in a binary symmetric channel with an error rate $$p$$, it is possible to transmit digital data with arbitrarily small probability of error up to a transmission rate of $1 + p \mathop{\log_2} p + (1 - p) \mathop{\log_2} (1 - p)$

We'll call this the optimal transmission rate. The error rate $$p$$ is the probability that the channel will corrupt a bit from 1 to 0 or vice versa. The transmission rate is the ratio of the number of data bits to the total number of bits used to represent them. If we employ error-correcting codes, the transmission rate would be less than 1 because we'll need extra bits for error correction. As a result, the number of bits used to represent them would be more than the number of data bits.

For $$p = 0$$, the transmission rate is maximum. That's obvious. Loosely speaking, if the channel is error-free, we do not need extra bits for error correction. The transmission rate is poorest when $$p = \frac{1}{2}$$. In this case, each bit received is completely random since the channel is just as likely to send 0 or 1 irrespective of the original bit sent by the transmitter. However, it might be surprising that as the error rate increases from $$0.5$$ to $$1$$, the optimal transmission rate increases. When $$p = 1$$, the optimal transmission rate is maximum again. It is easy to undersand this intuitively. At $$p = 1$$, the channel is guaranteed to corrupt each bit. The receiver can correct the error by inverting each bit in the received message, so we do not need extra bits for error correction in this case as well.

Now, let me get back to the puzzle I mentioned while beginning this post.

The company decided to keep Bob because he was more useful to the company. He helped the company to take 95% correct decisions. They simply did the opposite of what Bob recommended and made huge profits in the last ten years. Alex on the other hand helped them take only 80% decisions correctly, so he has to go. It's unfair but it's more profitable.

## Re: Infosys, TCS, or Wipro?

The 'Infosys, TCS, or Wipro?' post is doing the rounds again and some hatred as well as love is arriving on my email. That's fine. I've got pretty used to it in the last 5 months. If you try to say the truth, some people are going to call you arrogant and offensive. I would take hatred any day rather than needlessly sugarcoat things to please everybody.

I can understand when someone dislikes the way I have expressed the whole matter in that blog post. But I fail to understand the motivation behind any employee of these organizations trying to justify that working there is almost as good as working for a company where you can work with a team of very talented engineers. There have been plenty of arguments on the web. I'll discuss some of the points made in the arguments.

1. India needs IT services companies: The most popular argument by Indians has been that India needs IT services companies because they make a lot of money and boost India's economy. I don't understand why anyone would attack my post with this point when I have never said anything to the contrary. In fact, I agree with this point. However, in my opinion, students who have learnt their engineering well during the course, and now want to improve their engineering skills during work shouldn't work for one of these companies. They should join a start-up or a company known for hiring skilled engineers.
2. Business problems vs. engineering problems: Another popular argument has been that a software company is not a place to showcase your engineering talent. Many argue that it is a place to solve business problems, not engineering problems. I disagree with this very firmly. Business problems and engineering problems are not mutually exclusive. The reason why many employees of these companies feel that solving a business problem wouldn't involve an engineering problem is that they are not technically sound enough to even realize whether a particular problem needs to be solved with some concept they learnt in their engineering course. I've said this before and I'll say it again. Engineering problems are there in every software company. It needs the mind of an engineer to identify those problems and solve them correctly. Not all string parsing problems should be solved with a chain of string library functions stitched together. Some string processing and parsing work can be done more efficiently and reliably by coding a simple DFA. Not all data should be stored as records in an array. Some need to be stored as graphs. Knowing regular expressions can be dangerous if one doesn't know what kind of patterns they cannot express.
3. Business problems & engineering problems: If you want to solve business problems and keep your customers happy, Infosys, TCS, or Wipro might be the right place for you. If you want to solve business problems, keep your customers happy and learn a great deal of engineering while doing all these, you need to find another workplace where you can work with a team of skilled engineers who you can give you constructive feedback or criticism on your work.
4. Engineering in Adobe, Amazon, Google, etc.: A popular myth that prevails among many is that there is no engineering to do in the Indian offices of Adobe, Amazon, Google, etc. I'll reiterate that there is engineering to do in every software company, even in Infosys, TCS and Wipro. It really depends on the people whether they want to do engineering sincerely or not. Some people would somehow develop the required software by stitching together libraries and give up or look for less-efficient workarounds when a particular task requires inventing a new engineering solution. There is another kind of people who are ready to invent new engineering solutions with all the engineering knowledge they have acquired during college and professional life. They do not hesitate to re-invent the wheel when the existing libraries do not meet the requirements of the particular problem at hand. Such engineers are more in number in start-ups like Gluster, Parallocity, SlideShare, etc. and companies like Adobe, Amazon, Google, etc. These companies also collaborate with universties to learn new techniques and concepts to solve business problems. These companies do not look for less-efficient workarounds when faced with a brick wall. They challenge themselves and do everything possible to solve a problem in the best possible way. These are the places where freshers can hope to learn a great deal of engineering from people around them.
5. Passionate people can do engineering anywhere: Another popular argument is that it doesn't matter where you work. One can do engineering anywhere, be it Google or Infosys. I agree with this. But then, given a place like Adobe, Amazon, or Google where you can get very good feedback on your work from talented colleagues around you and another place like Infosys, TCS, or Wipro where clueless people around you would call you great because you solved a problem and hail you as a genius, where do you think you are going to learn more and improve yourself faster?
6. But everyone cannot join Adobe, Amazon, Google, etc.: Well, I never said that everyone should get into a reputed software product company. Not everyone wants to make a career in engineering. Some people have other goals in life. They just want a regular job. It sounds perfectly fine to me. My post was written for those who aspire to make a career in engineering. In my opinion, they should try to get into a reputed software product company or a start-up that is known to hire skilled engineers. If they aren't well prepared, the only thing they can do is to prepare well to fulfill their aspirations. Some people say that they should join Infosys, TCS and Wipro to earn a living while they are preparing and I think it's a great advice. I'll suggest considering contributing some new features or bug-fixes they would like to see in some open source project. Apache Incubator has a lot of budding projects. They can try solving problems at TopCoder, CodeChef, SPOJ, Project Euler, etc. All these things are good ways of preparing in my opinion.
7. Infosys, TCS and Wipro have good engineers: Many people have told me that there are good engineers in Infosys, TCS and Wipro as well. I agree. I never mentioned that 100% of the engineers in these companies don't do engineering. I mentioned that the majority of them don't do it. In fact, drawing from my personal experience, I quoted a figure that only 1 out of 200 are capable of engineering in these companies. Like most guess work, this figure could be wrong but I am pretty confident that the bigger picture I am trying to paint here isn't.
8. Training: Many claimed that I am wrong about the poor standard of training in Infosys, TCS, or Wipro. I must tell them that I have attended some of these training programmes. Among the many horror stories pertaining to training in these companies, I'll share only one with you to make my point. In the training assessments, the instructors set question papers containing problems with code that invokes undefined behaviour and ask you to predict its output. 'It invokes undefined behaviour' is not provided as an option you can select as the correct answer. Such training and knowledge is not only inaccurate but also very dangerous if you care about robustness and security of the software you create.
9. Meritocracy: A few people felt that I should have mentioned that these companies do not practice meritocracy. Anyone with sufficient number of years of experience can get a promotion in these companies. This is true. It didn't occur to me while writing that post. I was focussed on the popular myths about these companies that prevail among college students while writing the post.
10. Leaving Infosys, TCS, or Wipro: Some people commented that people like me just leave these companies and discourage others from joining them. They feel that we choose the easy way out. They would rather have us stay in these companies and improve them. Firstly, getting a job in a reputed company where you can get an opportunity to work on interesting engineering problems is not easy. You have to be passionate about your area of interest. You have to work and prepare yourself for it. Secondly, Infosys, TCS and Wipro were made by their founders with a particular vision of providing IT services. They have achieved what they wanted with great success. The improvements that you want to make in these companies may not be consistent with the vision of the founders.
11. Solving algorithm problems vs. editing configuration: This has to be the strangest argument I have come across. Someone mentioned that a person who solves algorithm problems earns no more than someone who only edits configuration files. After seeing both sides of the software industry, I find this false. Solving an algorithm problem is one thing. Solving an algorithm problem efficiently is an entirely different thing. I have seen people who can solve difficult algorithm problems efficiently earning at least twice that of an Infosys engineer. I have numerous examples for this: a friend who is solving problems to deliver the best news from the entire web to the users and another who writes algorithms for a cluster of Nvidia GPUs to do real-time analysis of network traffic to keep attackers out of the network. I have seen people solving algorithm problems in Topcoder, Codechef, etc. earning very well as software developers. While many argue that those fun problems tell you nothing about one's professional programming ability, I've found that people who successfully solve very difficult and contrived algorithm contest problems set by some of the most intelligent brains on the planet are actually pretty good at solving real software engineering problems as well. The toppers from these contests earn way more than someone who only edits configuration files.

To summarize, that post was meant for and only for people who have what it takes to work at a place where he can solve engineering problems. I have known many such people who were good engineers but weren't aware of the reality in companies like Infosys, TCS, or Wipro before joining them. That post was meant for these people. I devoted a couple of paragraphs in the previous post to make this clear but for some reason most people seem to have ignored them.

## Solutions to 'Loopy C puzzle'

In my blog post yesterday, I shared this puzzle:

Add or modify exactly one operator in the following code such that it prints exactly 6 dots.

int i;
for (i = 0; i < 6; i--)
printf(".");


Let me first list all the possible solutions I know.

1. for (i = 0; i < 6; i++)
2. for (i = 0; i < 6; ++i)
3. for (i = 0; -i < 6; i--)
4. for (i = 0; i + 6; i--)
5. for (i = 0; i ^= 6; i--)

The last solution in the list is not quite obvious and needs a little analysis to understand why it works. To generalize the problem, let us use n instead of 6. So, the loop becomes:

int i;
for (i = 0; i ^= n; i--)
printf(".");

If we use XOR to represent bitwise exclusive OR, first i is set to (n XOR i) before we enter the loop. Since, the initial value of i is 0, this amounts to setting i = n before we enter the loop.

Thereafter, every iteration prints a dot and sets i = n XOR (i - 1). If we try to represent two such consecutive iterations as one operation, this composite operation prints two dots and sets i = n XOR ((n XOR (i - 1)) − 1) where i on the RHS is the value of i before the pair of iterations and i on the LHS is the value of i after the pair of iterations complete. … (A)

Before we proceed further, note that

• k XOR 1 = k − 1 for an odd integer k. … (1)
• k XOR 1 = k + 1 for an even integer k. … (2)
• a XOR b is an odd integer if a and b have different parities. … (3)

I'm not presenting the proof of these results since they are very trivial. We'll use these results in the discussion below.

If n is odd, i is odd initially because i is set to n before we enter the loop. We'll show that i always remains odd and never changes for every pair of iterations.

i = n XOR ((n XOR (i − 1)) − 1)    … from (A)
= n XOR ((n XOR (i − 1)) XOR 1)    … from (1) and (3)
= (n XOR n) XOR ((i − 1) XOR 1)    … from associativity of XOR
= 0 XOR ((i − 1) + 1)    … from (2) and (3)
= i

Note that i begins as i = n. Since, i is set to n again after every two iterations, the loop never terminates.

If n is even, i is even initially because i is set to n before we enter the loop. We'll show that i always remains even and decrements by 2 for every pair of iterations.

i = n XOR ((n XOR (i − 1)) − 1)    … from (A)
= n XOR ((n XOR (i − 1)) XOR 1)    … from (1) and (3)
= (n XOR n) XOR ((i − 1) XOR 1)    … from associativity of XOR
= 0 XOR ((i − 1) − 1)    … from (1) and (3)
= i − 2

Since i begins as i = n and decrements by 2 for every two iterations, the loop terminates after n iterations thereby printing n dots.