maths and c++ 101

Dictionary attack on Linux passwd/shadow authentication scheme

Filed under: Uncategorized — luan @ 9:11 pm

1. /etc/shadow

On linux system user information are stored in /etc/passwd. This file is world-readable (readable by any user of the computer system, even nobody) So it is not a good idea to keep user passwords in it, even encrypted password.

The need to store (encrypted) password introduces the shadow file, which is /etc/shadow. It contains the password which has been encrypted with the salt, which is also in the shadow file.

contain of shadow file could be as follow:

luana:$1$TaORQ38u$Mfaih1b244CcesjU7Sj2T1:13975:0:99999:7:::

here, luana is the username

$1$ indicates we’re using a salt (TaORQ38u) and md5sum is being used to encrypt the key, $ signifies the beginning of the encrypted password (Mfaih1b244CcesjU7Sj2T1) and ends before :

2. Salt

salt is a string, publicly available (if you can see encrypted passwords you can see the salt), used to help with the password encryption process. Since encryption is a on-to function (or a surjection - see http://mathworld.wolfram.com/Surjection.html) two of the same words will encrypt to the same ciphertext. This means on a system with very large amount of user there will be a chance someone will use some very bad passwords (like “password” etc) and it will shows as two identical ciphertext in the shadow file.

Salt is mostly unique to each user. It is often the encryption of the time the user is added to the system (thus relatively unique for each user). This salt is mixed with the user password before we start the encryption. This means for any given two users it is extremely unlikely that they are BOTH added to the system at the same time and use the same password.

Simply put, salts allow the system to afford users to use the same passwords without having two identical encrypted passwords in its password file.

3. Note about writing programs on linux that uses crypt()

crypt is standard to most c/c++ compilers on linux system. This means you don’t even have to do #include <> in your program to use these functions.

Example program:

#include <iostream>
int main()
{
std::cout<<crypt(”kccL;pw_d:”,”$1$TMVRB39B”);
return 0;
}

When compiled on linux system (with GNU cryptography library installed) you would run:

[lubox@neo 3]$ g++ hw3.cpp -o o -lcrypt

Notice the -lcrypt option at the end. This will tell the compiler that you are using crypt function.

The above program when run will yield output:

$1$TMVRB39B$PUaDAsZctLWtj0kteqvBe1

with the salt the same, and the password is encrypted into the preceding bold part.

4. …

Comments (3)

March 31, 2008

Notes for comp 3053 and 2103

Filed under: Uncategorized — luan @ 11:55 pm

Your test will be on April the 8th, 2008. That is a week from today.

For COMP 2103 the test will cover chapter 4.5, 4.6 and all of 5 (follow the SLIDE numbering, not the book).

Tuesday April 1st: I will go over 4.5 and 4.6 (review). You will be turning in three assignments . We go to computer lab to demonstrate your program. I will grade and return Thursday so you can review for your test.

Thursday April 3rd: Last class before your test. We will go over Chapter 5. Make sure you have your questions ready.

For COMP 3053

Your test will cover chapter 5 and 6 on the 8th of April.
Tuesday April 1st: You’re turning in Assignment 7
There will be an in-class assignment on this day so make sure you don’t miss class. This assignment is on your slide, about breadth-first and depth-first search.

On Thursday we will cover chapter 6 (Gaussian elimination, horner’s rule…)

Dr. R’s cellphone number:

1-281… you didn’t actually think I was going to put his cell phone on the internet, did you?

Comments (0)

March 21, 2008

Hotel Infinity and 0.(9)

Filed under: Uncategorized — luan @ 11:00 pm

(skip to the line break for the impatience)

For Mathematic major, after you take all your Calculus and basic linear algebra you’d advance to Advanced Calculus. Advanced Calculus is quite a big leap from the “normal” mathematics you’ve been studying so far. Now you’re not learning mathematics to solve an equation, to find a value or evaluate an expression anymore. In Advanced Calculus (senior level courses at most College and Universities in America) you will learn about series and sequences and their properties and more. You’d be exposed to thinking very very fine (small) and also accept values and concepts that is larger than the largest thing you know so far.

It’s a big leap in understanding and requires a mature mind capable of abstract thinking. After you master the basics of sequences, convergence… of Advanced Calculus you’d be ready for the next step that is beginning Analysis. Intro to Analysis is a course designed to bridge the gap from Undergraduate Mathematics to a Graduate level training in the field. It’s abstract, it’s hard, it’s fun, it’s not compact(!)… you either get it or you don’t sort of thing.

This writing is about a classical problem in analysis. It’s would be quite straightforward to some people while does not seem “logical.” Your common sense may work for you or against you in this case. Let’s see…

——————————————————————————————

There is this hotel called Hotel Infinity. It has infinitely many rooms. Each of these rooms already has a guest in it. Now a new guest arrive.

None of the guests at the hotel will share a room with anyone. And no one is leaving either.

So how do you accommodate the new comer? Or can you accomodate him at all?

Logically (common sense perhaps?) if every single room in the hotel is filled then we can say the hotel is full! Meaning no more guests can be accommodated? Well but that’s the logic for a normal hotel, this is Hotel Infinity where we have infinitely many rooms remember? Having all the rooms filled and “NO VACANCY” is two very different thing here.
To accept this solution you must first accept that Hotel Infinity has infinitely many rooms. This IS the key. Infinitely many rooms means it WILL NEVER RUN OUT OF ROOMS (whether the newest room found has a guest in it or not).

To accommodate the new guest, you would tell the guest in room1 to move to room 2. Guest in room 2 move to room 3, room 3 move to room 4 and so on. You tell guest in room n to move to room number n+1 and son on. Because you have infinitely many rooms there will always be a room for everyone to move in to. By doing this you have just freed up room 1! Now just send the new guest to this room

Yes you just check a guest into a hotel where all the rooms are filled! Let your imagination roams

The problem is extended when Continue’Em Tours send there entire fleet of buses to your hotel. Their fleet has infinitely many buses each carrying infinitely many guests… You own Hotel Infinity, you can accommodate a lot (understatement) of people. But how do you accommodate Continu’Em Tours guests?

Comments (0)

Multiplication

Filed under: Uncategorized — luan @ 10:11 pm

Consider:
.              3128
.          x
.              2123
.       ————
(1)           9384
(2)         6256
(3)       3128
(4)     6256
.      ————-
.        6640744

This is 5th grade arithmetic. We all know how this multiplication works. Let’s look at the first row (1).
3 times 8 = 24 we write 4 and “save” 2.
3 times 2 = 6 we dump the 2 saved from the previous round so we write 8.

and so on.

But, why did we save 2 from 24?? When we first learn this multiplication at 5th grade I don’t think any of us ask this question. The reason is being you are working with decimals (base of 10). Meaning the digit 1 space to the left of the least significant bit (LSB) means how many 10s the value has. The digit 2 spaces to the left of the LSB means how many hundreds you have, and so on.

so for 1291 :

you have 1000 + 200 + 90 + 1

or simply, as agreed upon in base of 10, to be written as 1291.

Now, this is definitely not the only way to represent number! For some odd reason you would like to write 1291 in say.. base 5!

The answer is 20131
To verify you can see:

2*5^4 + 0*5^3 + 1*5^2 + 3*5 + 1*5^0
= 2*625 + 0*125 + 1*25 + 3*5 + 1
= 1291

Please take my word for it that this representation of 1291 decimal in base 5 is unique (it is). Now our question would be if the multiplication method we learned from 5th grade still work on number of a base other than 10? Let’s consider a small example of multiplying 29 x 67 (decimals).

29 (base 10) = 104 (base 5)
67 (base 10) = 232 (base 5)
.                         104
.                      x
.                         232
.           ————

Remember back in decimal everytime we have something larger than 10 (or the base) we do a carry out (or “save” or “remember”)? It is the same thing here. But instead of 10, everytime you have something larger than 5 you have to carry out 1 for each “5″ you have over.

so for 2 x 102:

2×4 = 8 write 3 carry 1
2×0 = 0 write 0 + 1 = 1
2×1 = 2 write 2

so for the first round we have

.           104
.          x
.           232
————-
.           213

Similarly for the other 2 operations we end up with this multiplication:

.           104
.          x
.           232
————-
.           213
.         322
.        213
————-
.        30233

For the final step of adding the 3 values together. When you add 2+2+3 this is 7 you write 2 (instead of 7) and carry 1 over to the next addition of 3+1. This becomes 3+1+1 = 5 so you write 0 and carry 1 over to the final addition of 2+0. For this last one 2+1 (carry out) = 3 you write 3.

This final value 30233 of base 5 corresponds to 1943 decimal. Which is indeed the product of 29 x 67 in base 10. :))

So there multiplication works with numbers of other bases also!

Comments (0)

to cool things off a bit :)

April 23, 2008

Dictionary attack on Linux passwd/shadow authentication scheme

March 31, 2008

Notes for comp 3053 and 2103

March 21, 2008

Hotel Infinity and 0.(9)

Multiplication