LINQ design interview question

LINQ is one of my favorite interview topics for many reasons. It allows me to check a candidate's ability to define logic, use SQL skills, showcase lambda expressions, distill the problem into easy steps and of course, see some code in action. Also, since LINQ code is generally quite compact, it is perfect for white boarding.

I was recently helping a friend solve a problem and felt that it could be modified to an excellent interview question. It has a bit of algorithm design, heavy use of simple to medium complex LINQ and is not more that 10-15 lines of actual code. Perfect.

Question: Given a class of students  (ID, Name, Grades) with results for at least 2 semesters, find the students whose Grades have significantly improved in the second semester as compared to the first. Bonus: List out top 25% of the students.

As the first step, let us define the rough algorithm for solving this problem:

1. Load Student data for first semester
2. Load student data for second semester
3. Merge Grades for each student from second semester into the first semester result set
4. For each student, calculate the grade difference for students whose grades have improved (you do not want to waste computational cycles for students whose grades have fallen)
5. For each student from 4 above, calculate the grade improvement percent
6. Sort the result by descending order of grade improvement percent
7. Select rows that constitute top 25% of students

Now, let’s define our POCO class that will represent the student data structure. The data structure has two parts: basic student properties (Id, Name, Grade) and some computational properties that we will use to solve our algorithm.

    public class StudentRecord
    {
        // basic properties
        public int Id { get; set; }
        public string Name { get; set; }
        public double Grade { get; set; }

        // computational properties
        public double GradeSecondSemester { get; set; }
        public double GradeDifference { get; set; }
        public double GradeDifferencePercent { get; set; }
    }

In addition to a Student record, we also need to a collection to hold these records. Let’s call it ClassReport:

    public class ClassReport
    {
        // some basic properties of a class
        public int Id { get; set; }
        public string Name { get; set; }
        public int SemesterId { get; set; }

        // list of student records for that semester
        public List<StudentRecord> Students;

        public ClassReport()
        {
            Students = new List<StudentRecord>();
        }
    }

For steps 1 and 2 of the algorithm, I am not going to focus on this blog. We will assume that we have a way to load this data (stubbed in our code sample below).

Step 1 and 2: Load Student data:

We will mock up our student data in this example. In real life, this data probably will come from a database or a web service call, etc. As you can see below, we generate some dummy student data for two different semesters. Note that the student Id’s need to match across (not really a hard requirement, but good to have for our demo purposes).

        static void Main(string[] args)
        {
            // Step 1 and 2: Load Student data
            ClassReport cr1 = MockSem1();
            ClassReport cr2 = MockSem2();

        }

        private static ClassReport MockSem1()
        {
            ClassReport cr = new ClassReport()
            {
                Id = 1,
                Name = "First Grade",
                SemesterId = 1
            };

            // add dummy data - in real life, this comes from database
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 1,
                    Name = "Ray",
                    Grade = 90
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 2,
                    Name = "Jack",
                    Grade = 80
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 3,
                    Name = "John",
                    Grade = 60
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 4,
                    Name = "Lisa",
                    Grade = 67
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 5,
                    Name = "Jill",
                    Grade = 94
                });
            return cr;
        }

        private static ClassReport MockSem2()
        {
            ClassReport cr = new ClassReport()
            {
                Id = 1,
                Name = "First Grade",
                SemesterId = 2
            };

            // add dummy data - in real life, this comes from database
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 1,
                    Name = "Ray",
                    Grade = 85
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 2,
                    Name = "Jack",
                    Grade = 95
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 3,
                    Name = "John",
                    Grade = 82
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 4,
                    Name = "Lisa",
                    Grade = 95
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 5,
                    Name = "Jill",
                    Grade = 96
                });
            return cr;
        }

Step 3: Merge Grades for each student from second semester into the first semester result set

Here is where our LINQ fun starts. In one of my previous post, I had explained how LINQ join works. Now would be a good time to review bunch of LINQ related interview questions and answers from the past.

            // step 3: Merge Grades for each student from second 
            // semester into the first semester result set

            // in-line merge; no need for a separate assignment
            // for each student in first semester report
            (from firstSem in cr1.Students
             // join to second sem class report
             join secondSem in cr2.Students 
                // on student id as the key
                on firstSem.Id equals secondSem.Id
             // assign second sem grade to first (via a select; clever)
             select firstSem.GradeSecondSemester = secondSem.Grade)
             // execute 
             .ToList();

As you can see from the LINQ statement, we join first semester class report with second semester and then do an in-line update of the first semester data structure’s GradeSecondSemester property.

Step 4: Calculate grade difference for students whose grades have improved

Now we need to process those students whose grades improved in the 2nd semester and update our data structure to reflect the difference:

// step 4: For each student, calculate the grade difference 
// for students whose grades have improved (you do not want 
// to waste computational cycles for students whose grades have fallen)
cr1.Students
    // find all students who did better in 2nd semester
    .FindAll(s => ((s.GradeSecondSemester - s.Grade) > 0))
    // and update their grade difference property
    .ForEach(x => x.GradeDifference = (x.GradeSecondSemester - x.Grade));

We use FindAll to find those students who have better grades and then loop for those records using ForEach to update the GradeDifference property.

Step 5: For each student from 4 above, calculate the grade improvement percent

// Step 5: For each student from 4 above, 
// calculate the grade improvement percent

// 5.a. calculate total difference sum
double gradeDiffSum  = cr1.Students.Sum(x => x.GradeDifference);

// 5.b. calculate percent for each row
cr1.Students
    // find all students who did better in 2nd semester
    .FindAll(s => ((s.GradeSecondSemester - s.Grade) > 0))
    // update grade percent
    .ForEach(x => x.GradeDifferencePercent = 
        ((x.GradeDifference * 100) / gradeDiffSum));

Step 6: Sort the result by descending order of grade improvement percent

By this point, I am hoping you get the gist of how to approach such LINQ queries. Sorting a list is a relatively simple operation as shown below:

    // Step 6: Sort the result by descending order of grade improvement percent
    var sortedList = 
        (from entry in cr1.Students
            orderby entry.GradeDifferencePercent descending
            select entry)
        .ToList();

Step 7: Select rows that constitute top 25% of students

We use TakeWhile here to keep selecting students till we reach our number.

    //Step 7: Select rows that constitute top 25% of students
    // 7.a. - sum of grade diff percent
    double gradeDiffPercentSum = 0;

    // 7.b - take as many rows as needed till we reach the 25% sum
    var bestStudents = 
        sortedList
        .TakeWhile(x => 
            ((gradeDiffPercentSum += x.GradeDifferencePercent) <= 25.0))
        .ToList();

    // 7.c account for the case where the first element is more than 25
    if (bestStudents.Count() == 0)
        bestStudents = sortedList.Take(1).ToList();

That’s it. You now have a list of top 25% students whose grades have improved in the second semester.

I am pasting the complete program here in case you like to see the whole thing in one shot.

The complete solution:

using System.Linq;

namespace StudentReport
{
 class Program
 {
    static void Main(string[] args)
    {
        // Step 1 and 2: Load Student data
        ClassReport cr1 = MockSem1();
        ClassReport cr2 = MockSem2();

        // step 3: Merge Grades for each student from second 
        // semester into the first semester result set

        // in-line merge; no need for a separate assignment
        // for each student in first sem report
        (from firstSem in cr1.Students
        // join to second sem class report
        join secondSem in cr2.Students
            // on student id as the key
            on firstSem.Id equals secondSem.Id
        // assign second sem grade to first (via a select; clever)
        select firstSem.GradeSecondSemester = secondSem.Grade)
            // execute 
        .ToList();

        // step 4: For each student, calculate the grade difference 
        // for students whose grades have improved (you do not want 
        // to waste computational cycles for students whose grades have fallen)
        cr1.Students
            // find all students who did better in 2nd semester
            .FindAll(s => ((s.GradeSecondSemester - s.Grade) > 0))
            // and update their grade difference property
            .ForEach(x => x.GradeDifference = (x.GradeSecondSemester - x.Grade));

        // Step 5: For each student from 4 above, 
        // calculate the grade improvement percent

        // 5.a. calculate total difference sum
        double gradeDiffSum = cr1.Students.Sum(x => x.GradeDifference);

        // 5.b. calculate percent for each row
        cr1.Students
            // find all students who did better in 2nd semester
            .FindAll(s => ((s.GradeSecondSemester - s.Grade) > 0))
            // update grade percent
            .ForEach(x => x.GradeDifferencePercent =
                ((x.GradeDifference * 100) / gradeDiffSum));


        // Step 6: Sort the result by descending order of grade improvement percent
        var sortedList =
            (from entry in cr1.Students
            orderby entry.GradeDifferencePercent descending
            select entry)
            .ToList();


        //Step 7: Select rows that constitute top 25% of students
        // 7.a. - sum of grade diff percent
        double gradeDiffPercentSum = 0;

        // 7.b - take as many rows as needed till we reach the 25% sum
        var bestStudents =
            sortedList
            .TakeWhile(x =>
                ((gradeDiffPercentSum += x.GradeDifferencePercent) <= 25.0))
            .ToList();

        // 7.c account for the case where the first element is more than 25
        if (bestStudents.Count() == 0)
            bestStudents = sortedList.Take(1).ToList();

        // do something with this result set
    }

        private static ClassReport MockSem1()
        {
            ClassReport cr = new ClassReport()
            {
                Id = 1,
                Name = "First Grade",
                SemesterId = 1
            };

            // add dummy data - in real life, this comes from database
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 1,
                    Name = "Ray",
                    Grade = 90
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 2,
                    Name = "Jack",
                    Grade = 80
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 3,
                    Name = "John",
                    Grade = 60
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 4,
                    Name = "Lisa",
                    Grade = 67
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 5,
                    Name = "Jill",
                    Grade = 94
                });
            return cr;
        }

        private static ClassReport MockSem2()
        {
            ClassReport cr = new ClassReport()
            {
                Id = 1,
                Name = "First Grade",
                SemesterId = 2
            };

            // add dummy data - in real life, this comes from database
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 1,
                    Name = "Ray",
                    Grade = 85
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 2,
                    Name = "Jack",
                    Grade = 85
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 3,
                    Name = "John",
                    Grade = 70
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 4,
                    Name = "Lisa",
                    Grade = 82
                });
            cr.Students.Add(
                new StudentRecord()
                {
                    Id = 5,
                    Name = "Jill",
                    Grade = 96
                });
            return cr;
        }
    }
}

How to time any function

One key aspect during performance testing is to time how long a function takes to execute. In this small post, I will show how to create a generic timing function that takes as argument the function to time and shows the time to execute along with the output of the function:

/// <summary>

/// Times the execution of a function and outputs both the elapsed time and the function's result.

/// </summary>

static void Time<T>(Func<T> work)

{

    var sw = Stopwatch.StartNew();

    var result = work();

    Console.WriteLine(sw.Elapsed + ": " + result);

}

To call the time, use the following invocation style:

Time(() => DoSomeWork());

LINQ interview questions part 2

Based on popular demand, I am posting a follow up post to my first LINQ interview questions article. In this post, we will follow a similar pattern of rapid fire interview questions and answers on LINQ concepts.

Question 1: How can you sort a result set based on 2 columns?

Assume that you have 2 tables – Product and Category and you want to sort first by category and then by product name.

var sortedProds = _db.Products.Orderby(c => c.Category).ThenBy(n => n.Name) 

Question 2: How can you use LINQ to query against a DataTable?

You cannot query against the DataTable's Rows collection, since DataRowCollection doesn't implement IEnumerable<T>. You need to use the AsEnumerable() extension for DataTable. As an example:

var results = from myRow in myDataTable.AsEnumerable() 
where myRow.Field<int>("RowNo") == 1 
select myRow; 

Question 3: LINQ equivalent of foreach for IEnumerable<T>

There is no ForEach extension for IEnumerable; only for List. There is a very good reason for this as explained by Eric Lippert here.

Having said that, there are two ways you can solve this:

Convert the items to list and then do a foreach on it:

items.ToList().ForEach(i => i.DoStuff());

Or, alternatively, you can write an extension method of your own.

public static void ForEach<T>(this IEnumerable<T> enumeration, Action<T> action) 
{ 
    foreach(T item in enumeration) 
    { 
        action(item); 
    } 
}

Question 4: When to use .First and when to use .FirstOrDefault with LINQ?

You should use First when you know or expect the sequence to have at least one element. In other words, when it is an exceptional if the sequence is empty.

Use FirstOrDefault, when you know that you will need to check whether there was an element or not. In other words, when it is legal for the sequence to be empty. You should not rely on exception handling for the check.

Question 5: Write a LINQ expression to concatenate a List<string> in a single string separated by a delimiter.

First of all, it is better to use string.Join to tackle this problem. But for interview purposes, this problem can be approached as follows:

string delimeter = ","; 

List<string> items = new List<string>() { "foo", "boo", "john", "doe" }; 

Console.WriteLine(items.Aggregate((i, j) => i + delimeter + j)); 

Question 6: Write a LINQ expression to concatenate a List<MyClass> objects in a single string separated by a delimiter. The class provides a specific property (say Name) that contains the string in question.

items.Select(i => i.Name).Aggregate((i, j) => i + delimeter + j)

Entity Framework transaction scope examples

Transactions as a core building block of entity framework. The DbContext object which we heavily use for interacting with the database uses transactions internally without you having to do anything extra. In case you need to manually provide transaction support, here is how you can do it.
In this post, I cover three cases in which transaction scope is being used to show rollback when an error occurs during an update of multiple entities:

1. when you have multiple save calls to the context;
2. when you have  single save with multiple object; and
3. transactions across multiple contexts.

Let’s first review our simple model and context object. To re-create this project, use Visual Studio 2010 console project with Entity Framework 5.0 RC bits from nuget.
Our model is a simplified version of a “Product” object and it’s definition look like this:

using System;
using System.ComponentModel.DataAnnotations;
 
namespace EFTransactionsDemo.Model
{
    public class Product
    {
        public int Id { get; set; }
        [Required]
        public string Name { get; set; }
        [Required]
        public DateTime DateAdded { get; set; }
    }
}

Our context definition looks like:

using System.Data.Entity;
using System.Data.Entity.ModelConfiguration.Conventions;
 
namespace EFTransactionsDemo.Model
{
    public class EFTDbContext : DbContext
    {
        public DbSet<Product> Products { get; set; }
         
        public EFTDbContext() : 
            base("EFTransactionsDemo")
        {
            // disable proxy creation 
            this.Configuration.ProxyCreationEnabled = false;
        }
         
        protected override void OnModelCreating(DbModelBuilder modelBuilder)
        {
            // Tell Code First to ignore PluralizingTableName convention
            // If you keep this convention then the generated tables will have pluralized names.
            modelBuilder.Conventions.Remove<PluralizingTableNameConvention>();
        }
    }
}

The main method (this is demo code; in production environments, please make sure to use proper programming paradigms, do error handling, parameter checks, etc.), calls three functions that demonstrate the use of transaction scope for the three scenarios I listed above.

using System;
using System.Linq;
using System.Transactions;
using EFTransactionsDemo.Model;

namespace EFTransactionsDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            // setup
            CreateDatabase();

            // transaction demo - 1
            // wrap multiple save calls within one transaction
            // and roll back on a bad one
            TestMultipleSaveCalls();

            // transaction demo - 2
            // wrap multiple adds and one save within one transaction
            // and roll back on a bad one
            TestMultipleAddWithOneSaveCall();

            // transaction demo - 3
            // multiple contexts in same transaction
            TestMultipleContexts();
        }

        private static void TestMultipleSaveCalls()
        {
            // good product
            Product goodProduct = new Product()
            {
                Name = "My awesome book",
                DateAdded = DateTime.UtcNow
            };

            // invalid product
            Product invalidProd = new Product()
            {
                Name = "My awesome book part 2"
                // note - no date added specified
            };

            // define our transaction scope
            var scope = new TransactionScope(
                // a new transaction will always be created
                TransactionScopeOption.RequiresNew,
                // we will allow volatile data to be read during transaction
                new TransactionOptions()
                {
                    IsolationLevel = IsolationLevel.ReadUncommitted
                }
            );

            try
            {
                // use the scope we just defined
                using (scope)
                {
                    // create a new db context
                    using (var ctx = new EFTDbContext())
                    {
                        // add the product
                        ctx.Products.Add(goodProduct);
                        // save
                        ctx.SaveChanges();

                        // add the invalid product
                        ctx.Products.Add(invalidProd);
                        // save
                        ctx.SaveChanges();
                    }

                    // everything good; complete
                    scope.Complete();
                }
            }
            catch { }

            // verify that we actually rolled back
            using (var ctx = new EFTDbContext())
            {
                Console.WriteLine(ctx.Products.Count());
            }
        }

        private static void TestMultipleAddWithOneSaveCall()
        {
            // good product
            Product goodProduct = new Product()
            {
                Name = "My awesome book",
                DateAdded = DateTime.UtcNow
            };

            // invalid product
            Product invalidProd = new Product()
            {
                Name = "My awesome book part 2"
                // note - no date added specified
            };

            // define our transaction scope
            var scope = new TransactionScope(
                // a new transaction will always be created
                TransactionScopeOption.RequiresNew,
                // we will allow volatile data to be read during transaction
                new TransactionOptions()
                {
                    IsolationLevel = IsolationLevel.ReadUncommitted
                }
            );

            try
            {
                // use the scope we just defined
                using (scope)
                {
                    // create a new db context
                    using (var ctx = new EFTDbContext())
                    {
                        // add the product
                        ctx.Products.Add(goodProduct);

                        // add the invalid product
                        ctx.Products.Add(invalidProd);
                        // save
                        ctx.SaveChanges();
                    }

                    // everything good; complete
                    scope.Complete();
                }
            }
            catch { }

            // verify that we actually rolled back
            using (var ctx = new EFTDbContext())
            {
                Console.WriteLine(ctx.Products.Count());
            }
        }

        private static void TestMultipleContexts()
        {
            // good product
            Product goodProduct = new Product()
            {
                Name = "My awesome book",
                DateAdded = DateTime.UtcNow
            };

            // invalid product
            Product invalidProd = new Product()
            {
                Name = "My awesome book part 2"
                // note - no date added specified
            };

            // define our transaction scope
            var scope = new TransactionScope(
                // a new transaction will always be created
                TransactionScopeOption.RequiresNew,
                // we will allow volatile data to be read during transaction
                new TransactionOptions()
                {
                    IsolationLevel = IsolationLevel.ReadUncommitted
                }
            );

            try
            {
                // use the scope we just defined
                using (scope)
                {
                    // create a new db context
                    var firstCtx = new EFTDbContext();
                    // create a second context
                    var secondCtx = new EFTDbContext();

                    // add the product to first context
                    firstCtx.Products.Add(goodProduct);
                    // save
                    firstCtx.SaveChanges();

                    // add the invalid product to second context
                    secondCtx.Products.Add(invalidProd);
                    // save
                    secondCtx.SaveChanges();

                    // everything good; complete
                    scope.Complete();
                }
            }
            catch { }

            // verify that we actually rolled back
            using (var ctx = new EFTDbContext())
            {
                Console.WriteLine(ctx.Products.Count());
            }
        }

        private static void CreateDatabase()
        {
            using (var ctx = new EFTDbContext())
            {
                ctx.Database.CreateIfNotExists();
            }
        }
    }
}

As always, please do leave your thoughts and comments. It is the user feedback that drives the product and blog better.

How to store user passwords using variable length random salt bytes with secure SHA512 cryptographic hashing functions

In modern web applications, the users of the site create accounts to gain access to customized data. When creating a signup/login process that requires a username and password, the credentials need to be stored and secured in a way that blocks unauthorized users. Furthermore, the passwords themselves need to be protected in case a hacker gets access to your data. In this post, we will review 3 schemes most commonly used today for storing and retrieving sensitive information.

Plain text scheme

The most basic (and unfortunately common) way to store user passwords is plain text. In this scheme, the login ID and the passwords are stored as plain text pairs in the database. When the user inputs his credentials, they are compared to the stored values and an appropriate response is returned. This is most commonly seen in legacy sites that have not yet upgraded their password schemes.

Username	Password
Joe	MyPassword
Nikhil	IThoughtThisWasASecurePasswordButIGuessIWasWrong
John	PasswordInPlainText

When a site sends you your actual password on the signup process or on retrieve a forgotten password, they are using this totally unsecure method of saving your password. Anybody who has access to the database (or the underlying storage) can see your password.

One way Hashed passwords scheme

The next level of password encryption is seen when developers first start learning about cryptography. They instantly gravitate towards algorithms that generate a one way hash of the password and store that hash in the database. Most common (but wrong) algorithms that get used are MD5 and SHA-1. These algorithms have been proven to be unsafe and should not be used. In the .NET world, the SDL (Security Development Lifecycle) has banned the use of these 2 algorithms. The recommended algorithm at this writing is SHA512.

Username	Password
Joe	CpYLOeOyIIGvruPyewcE49fOI9
Nikhil	roKMJYrGEKrp8z5Mah7J2T0cHcMAkZmxT6hplA3i1zTjidv0h
John	0oOW0dB36QHQaovguCL7fyjYYR

The disadvantage of such a scheme is that a dictionary or brute force attack and compromise your entire user base. But using this scheme is better than storing passwords in plain text. Also, it protects your user’s confidential information from prying employees who have access to the production database.

Let’s look at C# code to see how we can build this algorithm. The first function we will look at this the encryption algorithm itself. Then we will review how to use this function to Generate the password and then how to verify it.

/// <summary>

/// This function takes an input string and generates a 

/// one way hash using the SHA512CryptoServiceProvider

/// algorithm

/// </summary>

/// <param name="input">the input string</param>

/// <returns>a byte array of the hashed value</returns>

internal static byte[] GetHashInternal(string input)

{

    using (HashAlgorithm ha = new SHA512CryptoServiceProvider())

    {

        // Convert the input string to a byte array and compute the hash.

        byte[] data = ha.ComputeHash(Encoding.UTF8.GetBytes(input));

        return data;

    }

}

As you can see above, the framework provides a very easy way to generated hashed bytes of an input string. Now let’s look at the wrapper functions to generate the password and verify it.

/// <summary>

/// Takes an input string and generates a hashed string

/// </summary>

/// <param name="input"></param>

/// <returns></returns>

public string GetPassword(string input)

{

    // generate encrypted bytes

    byte[] data = GetHashInternal(input);

    // convert to string and return

    return ByteArrayToString(data);

}

public bool VerifyPassword(string input, string encPassword)

{

    // regenerate the encrpted bytes

    byte[] data = GetHashInternal(input);

    // convert to string

    string pass = ByteArrayToString(data);

    // compare 

    return (String.Compare(pass, encPassword, false) == 0);

}

/// <summary>

/// Generates a string using Hexadecimal for a given byte array

/// </summary>

/// <param name="data"></param>

/// <returns></returns>

private static string ByteArrayToString(byte[] data)

{

    // Create a new Stringbuilder to collect the bytes

    // and create a string.

    StringBuilder sBuilder = new StringBuilder();

    // Loop through each byte of the hashed data 

    // and format each one as a hexadecimal string.

    for (int i = 0; i < data.Length; i++)

    {

        sBuilder.Append(data[i].ToString("x2"));

    }

    // Return the hexadecimal string.

    return sBuilder.ToString();

}

The wrapper functions themselves are simple and should be self explanatory.

Random and variable length salted hashed password scheme

Salt, a random set of bytes, is used to make unauthorized decrypting of a message more difficult. A dictionary attack is an attack in which the attacker attempts to decrypt an encrypted message by comparing the encrypted value with previously computed encrypted values for the most likely keys. This attack is made much more difficult by the introduction of salt, or random bytes, at the beginning or end of the password before the key derivation.

Username	Password
Joe	CpYLOeOyIIGvruPyewcE49fOI9/s3WkFDM2KT+UYPyaNrIFqAu/roKMJYrGEKrp8z5Mah7J2T0cHcMAkZmxT6hplA3i1zTjidv0h
Nikhil	CTtLOq4Zx8oGGbg+3/0oOW0dB36QHQaovguCL7fyjYYR+d4wYhLCu/rRzZ5a2ENgy320+bWE8eLIHhxk1yGvNqKnGohIx0ubhJM=

This password algorithm scheme employs the following steps to secure the use data:

1. Generates a truly random number between 8 and 24. This will be used to determine the length of the random salt.

private static int GetTrueRandomNumber()

{

    // Because we cannot use the default randomizer, which is based on the

    // current time (it will produce the same "random" number within a

    // second), we will use a random number generator to seed the

    // randomizer.

    // Use a 4-byte array to fill it with random bytes and convert it then

    // to an integer value.

    byte[] randomBytes = new byte[4];

    // Generate 4 random bytes.

    RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();

    rng.GetBytes(randomBytes);

    // Convert 4 bytes into a 32-bit integer value.

    int seed = (randomBytes[0] & 0x7f) << 24 |

                randomBytes[1] << 16 |

                randomBytes[2] << 8 |

                randomBytes[3];

    // Now, this is real randomization.

    Random random = new Random(seed);

    // return a random number between 8 and 24

    return random.Next(8, 24);

}

2. Using this variable length, it then generates a random salt.

private static byte[] GetSaltBytes(string input, int saltSize)

{

    byte[] saltBytes = null;

    // get some random bytes

    using (Rfc2898DeriveBytes rdb = new Rfc2898DeriveBytes(input, saltSize, 1000))

    {

        // get salt

        saltBytes = rdb.Salt;

    }

    return saltBytes;

}

3. Next the user input is encrypted using this variable length random salt bytes using SHA512 crypto algorithm. In addition, the algorithm performs 1000 (or more) passes over the hashed output to provide a higher level of security.

private static string Encrypt(string input, byte[] saltBytes)

{

    // get input bytes

    byte[] inputBytes = Encoding.UTF8.GetBytes(input);

    // create salt + input array

    byte[] saltAndInput = new byte[saltBytes.Length + inputBytes.Length];

    Buffer.BlockCopy(saltBytes, 0, saltAndInput, 0, saltBytes.Length);

    Buffer.BlockCopy(inputBytes, 0, saltAndInput, saltBytes.Length, inputBytes.Length);

    // hash the salt and input

    byte[] data = GetHashInternal(saltAndInput);

    // append the salt length and raw salt to hashed data

    byte ss = Convert.ToByte(saltBytes.Length);

    byte[] finalBytes = new byte[1 + saltBytes.Length + data.Length];

    finalBytes[0] = ss;

    Buffer.BlockCopy(saltBytes, 0, finalBytes, 1, saltBytes.Length);

    Buffer.BlockCopy(data, 0, finalBytes, saltBytes.Length + 1, data.Length);

    // convert to base64 string

    string hash = ByteArrayToString(finalBytes);

    return hash;

}

internal static byte[] GetHashInternal(byte[] input)

{

    using (HashAlgorithm ha = new SHA512CryptoServiceProvider())

    {

        // copy into the return byte array

        byte[] data = new byte[input.Length];

        Array.Copy(input, data, input.Length);

        // process this atleast 1000 times

        for (int i = 0; i < 1000; i++)

        {

            // Convert the input string to a byte array and compute the hash.

            data = ha.ComputeHash(data);

        }

        return data;

    }

}

As you can see above, the Encrypt functions does a few steps. It first converts the user input string to bytes. It then inserts the un-encrypted salt bytes at the beginning of the user bytes. Next, using the SHA512 crypto algorithm, it runs a 100 passes over the salt+input byte array to generate a strong hash. Next, it appends this variable length random un-encrypted salt to the hashed encrypted salt+input byte array and also sets the first byte to hold the length of the salt. Lastly, it converts this to a Base64 encoded string and returns it to the user.

/// <summary>

/// converts a byte array to a base 64 encoded string

/// </summary>

/// <param name="data"></param>

/// <returns></returns>

private static string ByteArrayToString(byte[] data)

{

    string output = Convert.ToBase64String(data);

    return output;

}

/// <summary>

/// converts a base 64 encoded string to a byte array

/// </summary>

/// <param name="data"></param>

/// <returns></returns>

private static byte[] StringToByteArray(string data)

{

    byte[] output = Convert.FromBase64String(data);

    return output;

}

Now that we have the core algorithm under our belt, let’s look at the final routines on how to generate the password and verify it.

4. Generate the password and verify functions.

public string GetPassword(string input)

{

    // get random salt size

    int saltSize = GetTrueRandomNumber();

    // get random salt bytes

    byte[] saltBytes = GetSaltBytes(input, saltSize);

    // using this totally random and variable length salt

    // generate a crypto hash of the input string

    string hash = Encrypt(input, saltBytes);

    return hash;

}

public bool VerifyPassword(string input, string encPassword)

{

    // convert encrypted password to bytes

    byte[] finalBytes = StringToByteArray(encPassword);

    // get salt size

    int saltSize = Convert.ToInt32(finalBytes[0]);

    // now get raw salt 

    byte[] saltBytes = new byte[saltSize];

    Array.Copy(finalBytes, 1, saltBytes, 0, saltSize);

    // using this recovered salt

    // generate a crypto hash of the input string

    string hash = Encrypt(input, saltBytes);

    // check for match

    bool match = (String.Compare(encPassword, hash, false) == 0);

    return match;

}

The GetPassword() function is self-explanatory. You first generate a random number, get the variable length random salt bytes, use this to generate the password bytes, convert to Base64 encoded string and return this value.

The VerifyPassword() has a slightly different logic. Since each encrypted password uses a variable length random salt bytes, it first needs to get that information out of the encrypted password. Then using these salt bytes, it needs to re-run the encryption algorithm to regenerate the password. Remember, this is still using the one-way hashing concepts as that is the strongest way to ensure password safety.

In a production environment, you can do some additional variations where the un-encrypted variable length random salt bytes are inserted at the end, or a random location or in a separate encrypted string in a different column.

I hope this article will be helpful in helping you secure your customer’s private data from the prying eyes of the hackers. I would love to hear your feedback.