DEV Community: Hargunbeer Singh

How do structs work internally?

Hargunbeer Singh — Wed, 29 Dec 2021 09:00:19 +0000

Abstract
Table of Contents
Introduction
Memory Alignment
- Structure Padding
- Aligned Structs
- Advantages

Introduction

Structs are low-level data structures that store complex data structures. A struct consists of multiple fields that store data of different or the same data types. Structs are similar to arrays in some ways. Like arrays, the data of a struct is stored in a contiguous block of memory.

The variable to which an array is assigned becomes a reference variable to the first element of the array. Likewisely, the variable to which a struct is assigned becomes a reference variable to the first field of the struct. In arrays, you can navigate through the elements by adding the size of an element to the address of the first element.

For example, you can get the second element of an integer array by adding 4 to the memory address of the first element and you can do the same procedure multiple times to get consequent elements. The process of navigating through the fields of a struct is similar to arrays. Theoretically, you just need to add the size of the first field to its memory address to get the memory address of the second field. This is theoretical because it is not as simple practically.

Memory alignment

Memory alignment is the process of aligning the data in memory in such a way that is efficient and favorable for the processor. Data is aligned in memory by padding the data. Padding the data means adding some empty bits to the head or the tail of data in order to align it properly. There are some rules for structure alignment. Structure alignment is achieved by structure padding and both the processes complement each other.

Structure Padding

The memory alignment of the structure depends on the structure padding. The alignment and padding change according to the size of the various fields of a struct. There are two main rules to determine the padding and the alignment of the struct. To explain both the rules we would take the following struct as an example:

struct example {
    char i;
    int j;
} example1;

We need to know the size of the various fields of the struct to determine the structure padding. The compiler knows the size of the fields by their particular data type. The field i is of 1 byte because it is a char. The field j is of 4 bytes because it is an int.

The offset of a field of a struct is the amount of memory between its memory address and the memory address of the first field of the struct. In the struct mentioned above, the offset of j is 1 because there is 1 byte memory between the memory address of i and its own memory address.

The first rule of structure padding requires the offset of a field to be divisible by the size of the same field. For example, in the above mentioned struct the offset of j must be divisible by its size(4 bytes). For making its offset divisible by its own size, we need to add padding in between i and j. So to make the offset divisible by 4, we need to add 3 bytes of padding. So, there is 3 bytes of padding in between i and j.

The second rule of structure padding requires the size of the struct to be divisible by the size of the largest field of the struct. For example, consider the following struct:

struct dog{
    person* owner;
    int age;
} bruno;

The first field of the above struct is a pointer to another struct so its size is 8 bytes. The size of the second field is 4 bytes because it is an integer. No padding is needed in between owner and age because the offset of age is 8 bytes which is divisible by its size 4.

The second rule requires us to add padding at the end of the struct. The size of the struct(8+4=12) is not divisible by the size of the largest field of the struct(8 bytes). So to make its size divisible by 8, we will have to add padding at the end of the struct. We need to add 4 bytes of padding to make its new size divisible by 8. After adding 4 bytes of padding, its new size, i.e. 16 bytes is divisible by 8 hence following the second rule of structure padding.

Aligned structs

Data needs to be aligned properly for efficiency and performance of processors. If you have a 8-byte sized field in a struct, you should place it at a memory address divisible by 8. If you do not do so, the data stored in that 8-byte field would be called misaligned. Reading misaligned data is slow for the processor and the processor might not support a misaligned value, resulting in a program crash.

The first rule for structure padding requires the offset of the 8 byte sized field to be divisible by 8. You might need to add padding to make its offset divisible by 8. Suppose you have an integer before the 8-byte sized field. You would add 4 bytes of padding to make the offset divisible by 8. In this process, you have also made the memory address of the integer divisible by 8.

So in the process of making a field aligned at a memory address divisible by its size, you have aligned the struct by storing it at a memory address divisible by its alignment(the size of the largest field of the struct). The struct is considered to be stored at a memory address divisibly by 8 when its first field is stored at a memory address divisible by 8.

Advantages

There are a lot of advantages of memory alignment. Most processors work the best on memory aligned data. Memory alignment in structs is very advantageous because it prevents a struct field or a struct to be stored across two memory blocks. Fetching data from multiple memory blocks is very inefficient for the processor.

Also, the storing of data over two memory blocks might also chop the data. For example you are storing an array of structs in which the struct consists of a pointer and an integer. The struct is misaligned and has a size of 9 bytes. In case the array contains a lot of data, eventually the memory would all be used and the last instance of the struct would be chopped because there would be
likely no memory address divisibly by 9.

Bibiliography

A reddit post about structs in r/computerscience
- Special thanks to u/AuntieSauce, u/Poddster and u/JojoModding who helped me out in understanding the internal workings of structs

Remainder VS Modulus

Hargunbeer Singh — Sun, 12 Dec 2021 09:27:55 +0000

Introduction

Remainder and Modulo are two mathematic operations that are highly used in programming and computing in general. They both are represented by %, but they act differently, their differences are usually overlooked, but they are really important as now knowing the differences between the both might cause production bugs in an application.

Overview

Remainder and Modulo operations are a part of modular mathematics. Modular mathematics is usually used in clocks. The remainder is simply the number left after the division of two numbers, for example, 17 % 12 would be 5 as the number left after dividing 17 by 12 is 5. Its representation on a clock would look like this:

As shown in the diagram above, you first took a cyclic turn around the clock which accounted for dividing the dividend by the divisor 12. After a cyclic turn, you are left with 5 so you go forth 5 places, and 5 is the answer of 17 % 12. The Modulus operator would work the same way except that it would act differently when one of the operands is negative.

The Negative Number Game

Remainder and Modulus operators work the same way until and unless they are operated upon negative operands. The remainder operator would operate the negative operands in the same way as it operates the positive operands, it would just not consider the negativity of the number. On the contrary, modulus would operate differently, and here's how.

As proved earlier using clock math diagrams, 17 % 12 would result in 5 as the remainder. 17 % -12 would also result in the result being 5 as after one oscillation around the clock, 5 would be the answer. What about 17 % -12 using a modulo operator? We would need to use a different type of clock to depict the calculations.

So in modular mathematics, a clock hand's clockwise turn always increments the number of hours(value). So for carrying out 17 % -12 we would need a clock that increments the negative number -12, and it would look like this:

In the above figure, the clock is turning clockwise and the number is being incremented, so after a whole oscillation around the clock, we would have 5 left as the remainder, but we are using modulus so we will move the clock hand 5 steps further which results in the result being -7.

The dividend could also be a negative number with the divisor being positive. You would similarly solve that. Suppose -14 mod 12, so when we represent this on a graph, it would look like this:

In the above figure, we move the clock hand counterclockwise because the dividend is negative. After a single oscillation around the clock we just have 2 counter-clockwise clock hand turns left so the answer of this operation is 10, had the modulus been remainder in this operation, the answer would have been 2

In other words, the remainder operator returns the number of turns of the clock hand left after $n$ number of complete oscillations. The remainder is a result of modular division. The modulus operator returns the position of the clock hand after moving all the turns left. While using the modulus operator, we have to use all the clock hand turns left and then return the final clock hand position.

A point to be noted is that the clock is only shown because the divisor in all the operations is 12, you would not be able to represent an operation with some other remainder on a clock with 12 positions.

Which is Which

You must be thinking about how to differentiate between the modulus and remainder operator, given that they have the same sign % in code. The answer is: it depends. It depends on the programming language you are coding in. Different programming languages, consider the % symbol differently. For example, JavaScript, C++, and C# consider % as remainder operator whereas programming languages like Ruby consider % as modulus.

Where can this knowledge be used

Details are important. The details discussed above might make you think that they have no use, but yes they do! Knowing these details might help you with that production bug you just pushed or these details might be asked in a job interview.

Relational DBMS explained

Hargunbeer Singh — Tue, 21 Sep 2021 13:09:01 +0000

A relational database consists of rows and columns in a table, relational databases use SQL as their query language. They follow a relational data modeling paradigm. In a table, we need to uniquely identify each row, suppose it is a table of students in a university, you cannot uniquely identify a row based on the student's name as two students might have the same name, you cannot even uniquely identify a row based on the student's address as two students might be living at the same place, so you need to uniquely identify each student by a student ID that is unique to every student, this in the relational data modeling paradigm, is called the primary key, it is the key which uniquely identifies a row in a table.

In this university database analogy, you would have another table that would store the data for the classes. In the classes table, you also need a primary key that would uniquely identify each row in the table. The name of the class cannot act as the primary key as there could be two classes with the same name, likewise, the instructor cannot act as the primary key as an instructor might be teaching more than one class. So, here we would use the class id as the primary key to uniquely identify each class.

We can use the relational data modeling scheme of the relational databases to connect the two tables by their primary keys into a single table which would contain only the primary keys of both the tables. For example, we need to create a table that would store the enrollments which are the classes a student is taking. In this scenario, we could just link the primary keys of both the tables in a single table like this:

This can become complex when the number of rows of data increases so it is really difficult to scale. The new table that has been formed can be really useful as it provides us with the data about the attendees of a particular class as well as the data regarding the classes a student is taking. You can add another column to the new table formed by the merging of the primary keys of the two tables. For example, we can add a grade column to the newly formed table, and now we are having a lot of useful data in the newly formed table.

Note that the student id, as well as the class id, do not act as primary keys in the ENROLLMENTS table, and thus the enrollments table does not have a primary key, so we would go ahead and add a primary key to the enrollments table. We would use Enrollment ID as the primary key as it can uniquely identify rows of data.

The student ID is the primary key of a specific table and the class id is the primary key for a specific table. So, in the grades table, the student id is the foreign key for the students table and the class id is the foreign key for the classes table. A foreign key is a key in a table that is the primary key of another table's row. Foreign keys are really useful as you can use them to retrieve more data about a specific foreign key

For example, I am looking at the Grades table, and from there I get to know that the student with student ID 103 has only taken one class this semester, so I want to contact the student but the grades table does not have the student's address, but as the student id is a primary key of the students table, I would go on to look the students table with the primary key I found in the Grades table to fetch more information about the particular student, and there I would find student id 103's address. So the relationship between the students table and the grades table is one to many. The relationship between the Grades table and the classes table is many to one. A many to one relationship is a relationship between two tables, where many foreign keys relate to a single primary key in another table, like in this case, the same class ids in the grades table link to a single primary key in the classes table. The class ids in the grades table are the foreign keys for the classes table.

These types of relationships are formed to avoid redundant data in a database and also to avoid some other problems. As described earlier, by using foreign keys for a particular table, we can usually find more information about the particular foreign key. Foreign key relationships are possible due to the relational data modeling paradigms. What if we did not have a relation between the Grades and the Classes table and we had information about the Classes combined in the Grades table.

So, with relationship, we do not need to write all the data about a particular class in the grades table, but without a relationship, we have to write about the classes in the grades table, so a particular class id would have the same instructor and the same name which would result in redundant data. Redundant data is different as compared to duplicate data, duplicate data will have different primary keys whereas redundant data would have the same foreign key. Storing redundant data is a huge loss of space, and in this scenario, there would be hundreds of students taking the same class, thus we would have to write the instructor and the class name hundreds of times, wasting a lot of storage.

The other problem with redundant data storage is that it causes a lot of problems with updating and retrieving data from the database. So we continue the previous example, suppose the instructor for a particular class changed, you will have to change the instructor name hundreds of times in the Grades table because the name of the previous instructor has been written there multiple times. After all, there is redundant data. There are databases with millions of rows of data and updating the data in millions of rows is fatal for the speed as the CPU would be millions of times slower in completing the task as compared to updating a single row of data where the relationship between tables exists. If you do not update each row of data in a table that has redundant data, it may cause a lot of problems with retrieving data from the database.

Suppose the instructor changed and you did not update every row with the new instructor name, so when somebody wants to send an email to the instructor of a particular course, he would perform a query to the database for the specific class instructor, what if the query returns the first result which is the old data which was not updated and contained the name of the old instructor rather than the new instructor, thus causing a discrepancy in the application of the database. To avoid all this, we use relationships between different tables. There are some limitations for lots of reading and write queries per second, this is due to the relations between data and because SQL enforces ACID requirements.

How YouTube optimizes video delivery

Hargunbeer Singh — Tue, 21 Sep 2021 12:39:35 +0000

Introduction

YouTube is a massive video-sharing platform with billions of active users so YouTube needs to optimize everything on its platform. YouTube uses a lot of ways to optimize the performance of its apps. YouTube uses a lot of caching and has a very big network of servers over the planet. We will discuss how YouTube stores the videos and how it delivers the videos to its clients.

Overview

YouTube has a lot of video quality options like you can watch the video at a lot of different resolutions like 144p, 320p, 480p, 720p, 1080p, 2k, and 4k. So when a video is uploaded on YouTube, YouTube makes a lot of copies of the video in a lot of different resolutions and stores it on their servers. So when a client asks for a particular resolution, YouTube responds with a particular copy of the video. A particular video on YouTube is available on a lot of databases located at different places on the planet.

When a video is posted to YouTube from the USA, it is at first stored at the nearest server to the location it was uploaded from. When the same video is requested in Russia, YouTube requests the video from the USA servers and sends it to the requester from Russia. When the video reaches the Russian requester, a copy of the same video is stored on the Russian server so that it is quicker for the other Russian requesters to receive that video. YouTube might cache the video in the local area only if a certain amount of people request the video from that region. Receiving data from a far location consumes more time than receiving data from a near location, this is why YouTube caches the video in the local server/CDN.

When a video is uploaded to YouTube, YouTube breaks the video apart into very short clips for a better delivery time of the video to the client. It responds to the client with short clips of the actual video, so that it takes less delivery time and also because YouTube could fetch short clips of the video in the background while the client was watching a certain clip of the video. YouTube doesn't need to fetch the clips in proper order, sometimes it fetches clips of the video out of order and then couples them together for the client when the client is watching the video.

YouTube splits the video into the video graphics and the audio for content delivery optimization. A lot of people run YouTube in the background and are just hearing the audio of the video, this happens in a lot of cases like when you are listening to a podcast or music on YouTube. YouTube listens for this case and then just sends the audio to the client and does not send the video at all to the client, this saves YouTube a lot of bandwidth and also increases the speed of delivery of the content as just the audio is being sent which is a lot smaller in size than the audio and video combined.

Conclusion

YouTube has a crazily complex infrastructure and the fun fact is that when you post a video to YouTube, it will end in 100s of pieces and at lots of locations on the planet, so at last your video would have 1000s of copies on the YouTube servers. Other video streaming platforms like Netflix, Amazon Prime Video, Twitch, etc. use a similar technique for video streaming. The complexity of the infrastructure increases manifold as an app grows.

Programming languages are overrated!

Hargunbeer Singh — Mon, 20 Sep 2021 01:31:12 +0000

Edit: I posted a video about this topic here so you can go watch that if you do not like reading :)

“Most People” go on to learn to use programming languages and frameworks rather than learning the core concepts of how a particular platform (say the web) works. “They” do not go on to learn how code gets executed in a programming language they rather pay more attention to learn how to code.

I’ll support my opinion with an analogy to convince you - if you teach a person how to catch fish using a spear, the person would catch the fish and use the fish for nutrition but if you teach a person how exactly a spear works, or in other words, teach them the craft to use any weapon, the person would be able to feed himself for his whole life; even if the fish disappear, the person would be able to hunt other animals for food.

I'll also support my analogy with mathematics, as it is the only art that never lies, suppose a person takes 5 years' hard work to master the weapon craft and catches no fish what so ever in that time; on the contrary, a person who just knows how to "catch" fish would catch maybe 5 fish a day so the person would in total catch 9125 fish(5*365*5) in 5 years.

When the person who is a master of the craft would start to catch fish, I am pretty sure that he would be able to catch 1000 fish in a day, so as basic math says, the person would be able to catch 10000 fish(10*1000) in 10 days. This proves that a person who masters the core craft would earn more in 10 days than the normal person earns in 5 years. Also, that talent stays for ever, so you can catch a 1000 fish or chicken or crabs for the rest of your life everyday.

Such is programming you teach a person how to write a timer in JavaScript, he will be able to sell that timer code for some money once; but if you teach the person how does programming and problem solving work at its core, the person will be able to feed himself for life. What I wanted to express via this short article is that - don’t go after learning more and more “programming languages”, go after learning how a particular niche works IN DEPTH.

If you know the concepts well you can easily implement the system design easily in code. As very less people learn these concepts, it is an opportunity for you to become one of the top programmers in a niche.

Data Structures for Dummies

Hargunbeer Singh — Wed, 08 Sep 2021 14:46:58 +0000

Introduction

A data structure is a way how data is stored in the memory, it is is really important to store your data in the correct data structure for optimal algorithmic performance. In technical words, a data structure is a data organization, management and storage format that enables efficient access and modification. It is an algebraic structure about data. Using a data structure, makes it easy to retrieve and read data from the memory. They are generally based on the ability of a computer to fetch and store data at any place in its memory. A simple example of a data structure is an array, it is used to store a series of values in memory.

Types of Data Structure

Choosing the right data structure for performing a particular task is a choice that pays you off in the future. The use of right data structures make a computing task a lot more efficient and easy to code. There are a lot of data structures used for different types of tasks, some of the popular data structures are described below.

Array

Arrays are a series of values stored in memory. One-dimensional arrays are the arrays which just have the values stored in a series in them and do not have other nested arrays inside them. One-dimensional arrays are also referred to as vectors. We can point to a value in an array using index, most programming languages start indexes with 0, for example we can reference the first value in an array called hobbies by hobbies[0]. An array is stored in memory in the following way: its consequent values are stored in the memory as corresponding data types, like an array containing 4 values would store the values as their corresponding data types in memory from lets say memory location 1000 to 1003, although they are stored as common data but still the compiler knows that all the values are a part of a single array. An array of values is fixed and cannot be enlarged to add more values. Arrays also need to be stored in order in memory which makes it hard to add a new value(*do not relate to pushing a value into an array)

Strings

A string datatype is also stored as an array in memory, lets suppose the string Hello World, the compiler would store the string by splitting it into individual characters, so H would be stored in memory location 1ooo and the space would be stored in memory location 1005 and so on, the compiler denotes the ending of the string by a null character, giving the compiler a signal that it needs to stop reading the data from the memory, and when the compiler fetches the data from the memory, it merges the individual characters and forms a string.

Matrix

We can use arrays to make one-dimensional lists but sometimes we need multi-dimensional data structures to store data like the value of each pixel on a screen or the data stored in a spreadsheet, a multi-dimensional data structure is called a matrix. It is an array of arrays, so it contains a series of arrays which further contain a series of values. For example: A 3 by 3 matrix would be an array of 3 sub-arrays which are an array of 3 values each. They are stored in memory similar to how arrays are stored in memory. The values of sub-arrays of a matrix are stored as their corresponding data types in the memory and when the compiler reads them, it knows that they are the sub-arrays of a matrix. Matrices are not only limited to two or three dimensions, they can be of any dimensions, so a five dimensional matrix would have 5 layers of arrays, so you can point to a value in a five dimensional array like this hobbies[3][5[8][4][5], higher level matrices are used to store relatively complex and more nested data sets.

Struct

It is a great programming practice to store a set of related variables together, like you should store the data about an employee, like his age, salary and designation in a struct as all these variables are related, objects(as popularly called in programming languages) are a higher level implementation of structs. For example: you can retrieve the age of an employee from the memory from the employee struct by employee.age. We can even make arrays of structs that we define, and structs are automatically bundled up in memory. So in an array of structs, we can retrieve a struct by pointing to its index in the array and then to retrieve a value from the specific struct we would point to the variable name. Structs can be used to make more complex data structures which avoid the problems with arrays, i.e. new values cannot be added in the middle of an array because they are stored in order in memory. These structures are called Nodes

Node and Linked List

It is a type of struct that stores both the variable and a pointer in itself. A pointer is a special variable that points to a location in memory. Using node, we can create a linked list, which is a complex data structure which is flexible and stores many nodes. A linked list stores multiple nodes by pointing each node to the next node in the linked list. A linked list eliminates the problems of an array as it is very flexible in storing nodes, the nodes do not need to be stored in a particular order and two nodes can have other data between them. The pointer in each node comes into play in joining the linked list, so suppose we have a linked list with three nodes, the first node would point to the second node's location in memory and the second node will point to the third node's location in the memory, if the third node points back to the first node's location in memory, that means that the particular linked list is a circular linked list.

If the value of the pointer of the last node is null, then the linked list ends there. We can insert new nodes in the middle of the linked list, unlike arrays, as we just need to change the pointer value of the previous node while adding another node. Developers do not need to worry about the pointer values, that is work for the compiler and the developer can just visualize linked list by a layer of abstraction. Linked lists, due to their flexibility, can also be easily re-ordered, trimmed, split, reversed, etc. Linked lists are really useful for algorithms like sorting algorithms. Because of the flexibility that Linked Lists offer, many more data structures are build on top of linked lasts, the most famous ones are queues and stacks.

Queues

A queue is a data structure that follows a first-in first-out(FIFO) approach. As its name states, FIFO is an approach where the first arriver is served first. It is built upon linked lists. Suppose in a linked list, we have a pointer that points to a bank queue visualized like this:

So the bank queue is a queue data structure where Steve points to Michael, Michael points to Anna and Anna points to Della, Della is the last node in the list as its pointer value is null. So after we have served Steve, we would read Steve's next pointer and dequeue Steve from the queue. To add a new node to the linked list, we would have to traverse down the linked list until we reach the node with pointer value null, and then we add the new node to the end of the linked list and update the pointer values of the former last node of the linked list. Adding a node to the queue is also called enqueueing.

Stacks

Stacks are data structures build upon linked lists. They follow a Last-in First-out(LIFO) approach. As its name states, LIFO is an approach where the last arriver is served the first, and the first arriver is served the last. An analogy to explain that can be a pile of papers, so the paper that has been piled the last would be picked up the first, and the paper that was piled up the first would be picked up the last. Adding nodes to the stack is called pushing data to the stack. Removing data from the stack is called popping data from the stack.

Trees

Trees are data structures built on linked lists; a tree data structure is just a node with multiple pointers. This data structure is used in the implementation of a lot of algorithms. Programmers generally do not consider looking at and evaluating the list of pointers and rather use a layer of abstraction to conceptualize trees like this:

The top most node of the tree is called the "Root". Children nodes are the nodes a particular node points to. A parent node is a node which points to other nodes(children nodes). The nodes which do not have any children nodes in a tree data structure, they are called the leaf nodes. A tree data structure whose nodes can have maximum two children nodes are called binary trees. Their is only one way roots are connected to leaves and there cannot be a tree in which the roots link to leaves and the leaves link to roots.

Graph

Graphs are used to store data that links arbitrarily. This type of data usually uses loops. A branch of mathematics - Graph Theory studies the graph data in detail. A graph is a data structure in which nodes are pointed to each other. In graph data structure too, the programmer doesn't need to care about the pointer values of various nodes; the programmer can usually visualize the graph with a level of abstraction as:

The above image is a real life example of graph data, it represents all the paths a soldier can take to reach a particular place(node). Graph theory studies the paths(node pointers) and finds statistical data from the graph to find efficient techniques to perform various functions. Dijkstra's algorithm is a vital part of graph theory and it is an algorithm to find the shortest paths between nodes in a graph, in this case the shortest distance to reach a particular place. Graphs, other than computer science, are also used in real world scenarios, like finding the shortest distance between two cities or finding the shortest path to attack an enemy trench in a war.

Others

These are the most popular common data structures, on top of these data structures, programmers have build more data structures with specific functionalities like red-black trees and heaps.

Conclusion

You must use data structures for writing efficient code and algorithms. Programmers do not need to implement these data structures from scratch as most programming languages have default packages which have implementations for common data structures.

Cryptographic frequency Analysis explained

Hargunbeer Singh — Tue, 07 Sep 2021 07:19:06 +0000

Frequency Analysis is the study of frequency of letters or group or letters in a ciphertext. This method is relatively older to the newer methods of cryptanalysis. This method is used to break classic ciphers, this method is really useful in breaking substitution ciphers. It is based on the fact that certain letters or group of letters in a specific language text occur with specific frequencies. There is a distribution of the frequencies of letters that occur in a particular language. For example: the letters E,A,T and O occur the most in a piece of text in the English language. Similarly, the letter pairs - TH, ER, ON and AN are the most common in a piece of text in the English language, these pairs are reffered to as bigrams.

In some ciphers, the properties and patters of the plaintext is preserved in the ciphertext, and these patterns can easily be studied and then the cipher can be exploited. The ciphertext usually retains the properties of the plaintext when a single letter always gets encrypted to the same ciphertext letter, this usually occurs in substitution ciphers. This type of attack is called ciphertext-only attack. Ciphertext-only attack is the attack in which the cryptanalyst just has the access to the ciphertext and nothing else. The cryptanalyst, in some cases might also know the language of the plaintext, where the cryptanalyst can use techniques like frequency analysis and index of coincidence.

When a plaintext is encrypted using a substition cipher, and the cryptanalyst know the actual language of the plaintext, the cryptanalys can easily find frequency distribution and sequences in the ciphertext in most cases. For example: if a ciphertext contains a high frequency of R in it and the plaintext language was English, the cryptanalyst would know that R would most probably be E, T or A in the plaintext as these letters occur the most in English, he would still need to try more combinations but frequency distributions make the combinations to try a lot lesser.

Cryptography explained

Hargunbeer Singh — Tue, 07 Sep 2021 06:18:31 +0000

Introduction

Cryptography is the study and practice of techniques used for secure communication in the presence of adversarial behavior. An Adversary is a malicious entity that does not want the users of a specific cryptosystem to communicate and achieve their goal. The adversary might try to corrupt the data or retrieve the information in the data.

Cryptography is about constructing and analyzing ways and protocols that prevent third parties from reading private data while it is transmitted to the desired receiver. The pillars of cryptography are confidentiality, data integrity, authentication and non-repudiation(highly used principle in blockchain). Ciphers, Encryption and Cryptographic hash functions form a huge part of cryptography. Cryptography is based on the disciplines of mathematics, computer science and physics. Cryptography is highly used in, sending emails and messages, secure credit card transactions, cryptocurrencies, blockchains, storing data and and military communications.

Overview

Encryption is a modern day implementation of cryptography, It is the technique of converting readable information into something completely unreadable, such that only authorized parties can convert the unreadable information back into readable information, thus increasing communication security. This is made possible as the algorithm to decode the unreadable pseudorandom text is only shared in-between the authorized parties. Since the development of cryptographic machines like the enigma and Lorenz cipher machine in the world wars, cryptographic techniques have advanced manifold as its use cases have also increased. Cryptography is used everywhere, the messages sent via social media apps are also encrypted so that no hacker in between can intercept the messages. Cryptography, over several years, has become more term of computer science than mathematics as it is used a lot in computers. Modern cryptography is heavily based on mathematical theory and computer science practice, cryptographic algorithms are designed around computational hardness assumptions which states that an algorithm cannot be broken efficiently(in context to time). Well designed cryptographic algorithms cannot be broken in most cases, and the only way to break a cryptographic algorithm is bruteforce, which is a trial and error method of finding out what the encrypted data is, in the case of bruteforce, it depends on the amount of computational resources allocated to breaking the algorithm. There are some cryptographic algorithms which cannot be broken even by bruteforce, like OTP(one time pad).

Terminology

In cryptographic literature, the names "Alice", "Bob" and "Eve" are frequently used. "Alice" is the sender and "Bob" is the receiver, whereas "Eve"(eavesdropper) is an adversary. You can assume names in cryptographic literature according to a specific scheme. You have to name the entities in alphabetical order, like first a name starting with "A", then "B","C","D" and so on, but you skip the name with "E" as a common entity because it is the adversary. For example: Alice, Bob, Charlie, Darwin, Finn and so on.

Cryptography is the practice of cryptographic techniques whereas cryptology is the study of both cryptography and cryptanalysis. Cryptolinguistics is the study of characteristics of languages that have some application in cryptography or cryptology. For example: frequency data, letter combinations(linguistics), patters, etc.

Disciplines

There are a lot of disciplines under cryptographic, there is assymetric key encryption, symmetric key encryption, substitution cipher and a lot more.

Cryptographic Hash functions
Cipher
ciphertext
codetext
cryptanalysis

Clickjacking explained

Hargunbeer Singh — Sat, 04 Sep 2021 14:25:33 +0000

Introduction

Clickjacking, also referred to as UI redressing, is a malicious technique of tricking a user into clicking something different from what the user actually perceives. The user clicks on seemingly harmless objects, but actually they are a trap and are something completely different. Using clickjacking, sensitive information of the victim can be exposed, also the attacker can take control over your computer. The attacker redresses the malicious UI into something completely different that looks harmless, that is why clickjacking is also referred to as "UI Redressing"

Clickjacking is an instance of the confused deputy problem in which the user is tricked into thinking that a malicious object is harmless, by disguising the malicious object. The users are then tricked and made to click the malicious objects that trigger malicious actions. Their is a privilege escalation of the attacker when the victim clicks the malicious object. Clickjacking is used for a plethora of web attacks, like CSRF. Clickjacking is performed on the attacker-maintained website, so a clickjacker can only harm a user and not a server.

Example

The attacker could disguise a money transfer form into something else, and when the user enters his data, the money transfer would occur, thus causing the victim a loss.
The attacker could disguise a malicious ad link as the play button on a video and direct you to an ad.

Preventive Measures

There are both client-side as well as server-side measures to prevent clickjacking.

Client-Side

Clickjacking can be reduced on the client side by installing some plugins in browsers like NoScript, NoClickJack and GuardedID.

Sever-side

There are various server-side ways to protect your users from clickjacking on your website.

Framekiller

You can protect your users from UI redressing(frame based clickjacking) on the server side by including a framekiller JavaScript snippet in those pages which you do not want to be included inside frames on different websites. This type of protection against clickjacking is not very reliable, particularly on IE, where this kind of measure can be circumvented by including the targeted page inside an <iframe security=restricted> element. This is a design issue in IE.

X-Frame-Options

X-Frame-Options is a HTTP header that can be used to indicate whether or not a particular website should be allowed to render a page in an iFrame, etc. Websites can use this to avoid clickjacking attacks as it ensures that a website's content is not embedded into other sites. X-Frame-Options provide only partial security against clickjacking because the header will only be in effect if the user's browser supports it. You can allow certain website to embed your webpage on their website by specifying it, you can also allow the same origin web pages to embed a web page.

Content-Security-Policy

The frame-ancestors directive of the HTTP CSP(Content-Security-Policy) specifies valid elements that are allowed to embed a page using iFrames etc. This is similar to the X-Frame-Options and its values are also similar to the values of X-Frame-Options. The only difference is that X-Frame-Options header just checks top-level document location that is the website URL whereas the frame-ancestors directive checks each ancestor(parent), if the ancestor does not match with what is defined in the CSP, the load of the frame is cancelled. Also the CSP obsoletes(out fashions) X-Frame-Options header, if both the directives are specified on a web page, CSP is given the priority and the X-Frame-Options header is ignored.

Cross Site Request Forgery Explained

Hargunbeer Singh — Fri, 03 Sep 2021 13:12:40 +0000

Introduction

CSRF stands for Cross Site Request Forgery. It is an attack in which the attacker pretends to be an authenticated user on a website and sends unwanted requests to the website, and the website backend thinks that the authenticated user is making the request. This can be done in many ways. The attacker could steal the cookie of the authenticated user and pretend to be the user on a specific website and perform any malicious requests to the website, like transferring money, deleting an account, etc. Another way to perform CSRF is to maliciously include malicious parameters in a link from a website to the victim website. A website is vulnerable to CSRF if it authenticates the user using GET requests. A malicious website could also have disguised a form which performs CSRF.

Overview

The web works by sending data to and fro. Their are mainly two ways of sending data: GET and POST request. When you use GET request, the data which is sent as a parameter which is visible in the website address. GET requests are used to fetch data from a server. When using POST request, the data is sent to the server, but it is not visible in the website address. POST requests are used to send data to the server. Example: if you are watching a youtube video, the link would be like youtube.com/watch?v=videoID, here the video id is a GET request parameter, and if you copy paste the link and send it to a friend, when she clicks on it, she would also get the same page. Whereas in POST request, when you post a comment, it is not visible in the search bar address, so even if you copy paste the link and send it to a friend, she would not post the same comment by clicking on that link, unlike she got the same page as you in the case of GET request.

To perform CSRF, the attacker has to authenticate the user on the website via his malicious webiste, that can be done by making certain requests to a particular website in the background. Using GET requests, the attacker can perform CSRF by sending the data in parameters to the website to authenticate the user. When using POST request, the attacker sends the data to a website unnoticed by the user. GET requests are a boon to an attacker as the victim just needs to click the link and CSRF would be performed, this is why websites do not authenticate or perform important actions by storing data in the link parameters.

Examples

For example: You could hide a tweet form on your malicious website, so when the user clicks a button to post a comment, the event is triggered to tweet the data in the hidden form instead of posting the comment. The attacker authenticates you to twitter in the background using web workers and then sends the POST request to the twitter API to tweet the content from your account, and the tweet might be controversial, and that can cause trouble if you have a great following. The attacker can also make you transfer a million dollars from your account to his account using CSRF.
A malicious website could also have disguised a form, for example: a money transfer form could have been disguised as a credit card linking form, where the amount field is hidden, and when you authenticate your credit card, and click the submit button, the POST request will go to the bank API instead of going to the malicious website API, thus performing the money transfer from your bank account. You would be authenticated to your bank in another tab or in the background.
When you post a comment on a malicious website, the website might impersonate you on another website in the background or in another tab, and could do anything on that website by a POST request, like deleting your account.

Preventive Measures

'Referrer' Header

Preventive measures against CSRF were introduced in the HTTP protocol. The preventive measure was to include a Referrer header in the HTTP request, so that the API knows from which website is the HTTP request coming from. But that preventive measure did very less impact to CSRF because most of the users have ad blockers or privacy plugins which just do not allow them to send the Referrer header to the API.

One-time key

Another preventive measures against CSRF is a one-time key, which a lot of websites use these days. One-time key is also called the nonce. Web apps use one-time key to authenticate POST requests or any commands that will have a permanent effect on the user. One-time key is near impossible to break, as it is something completely random, and the attacker cannot authenticate to the website without the nonce. The nonce is sent to the user using authentication apps like Google authenticator or via SMS on the user's phone number. Brute force can also not break one-time key because one-time keys are generally valid for a short period of time.

Same-Origin Policy

The Same-Origin Policy forms a great part of the browser's security policy. Same-origin policy states that data on a particular api on a specific domain can only be accessed by requests from the same domain. This forms the barrier against CSRF, as the requests from other websites won't be able to impersonate the victim on another site. The website web servers should only allow their own domain to make HTTP requests for executing certain commands on the website on the web server.

Synchronizer token pattern

Synchronizer token pattern is also referred to as CSRF token. It is a technique in which the server generates unique and random tokens to authenticate its users' requests. It needs to be unique for each POST request. CSRF tokens should be such that they are only accessible to a specific website. Due to CSRF tokens, the attacker is unable to make POST requests from a malicious origin as the attacker would not have the user's CSRF token. This is made possible due to Same-origin policy. Though, it is not mandatory that CSRF token need to be unique for each request, but the CSRF tokens should only be valid for a short period of time, preventing the attacker to brute force. The CSRF tokens must be declared invalid when a user session expires, because if you do not make the CSRF tokens invalid, the attacker could brute force the token, and then use it to exploit the user again in consequent sessions.

CSRF Phishing attack

A common type of CSRF attack would take place like this:

The attacker creates a new account on a website.
The attacker makes the new account prone to Self-XSS on the website.
The attacker leads the victim to a phishing site, which logouts the victim out of the website on which the CSRF is being performed.
The victim is logged in to the CSRF-prone website with the attacker-created account. The victim is logged in, as the attacker tricks the victim to click a button on the phishing site which leads to the CSRF-prone website.
Self-XSS is executed in the attacker-created account on the victim's computer which cleverly asks the victim to input his password
The password is sent to the attacker
The attacker authenticates the user to the website using the credentials entered, so that the user thinks that nothing has happened.

🍪Cookies and Cookie Tracking Explained

Hargunbeer Singh — Mon, 30 Aug 2021 12:28:51 +0000

Introduction

A cookie is a small piece of information stored in the client's computer by a particular website via a web browser. They are used to personalize a user's experience on the particular website. It usually contains the user's preferences and inputs. A user can customize their web browser to accept, reject or delete cookies. Cookies can be modified at the server level by using the Set-Cookie HTTP header. It can be modified at the client level by using document.cookie in JavaScript.

Cookies are shared to the server on consequent HTTP request. When you perform a HTTP GET request, the server returns you the webpage(HTML, CSS and JavaScript) along with some cookies which would be populated with data as you surf the specific web page. When you form another HTTP request to the server, the cookies which were populated with your data(preferences) are sent to the server. Thats how cookies help in storing the user's preferences. Cookies transactions take place between the user and the server using the Set-Cookie header.

There are two types of cookies - First Party Cookies and Third Party Cookies. First Party cookies, as the name says, are the cookies used by the website you are surfing to improve user experience. Third Party cookies are the cookies which are used by third-party services to improve the user experience, these are mostly advert companies, which improve user experience, like Google Ads which suggests you proper websites in its search ranking.

Cookies are not stored as code on the user's machine, it is rather stored as simple files, which cannot be executed. Stored cookies cannot even manipulate the elements of your screen, it can't even access your mic or webcam. The only worry about cookies is thier system of allowing data(preferences) to be sent to the server without anybody noticing.

Examples

When you turn on the dark mode on YouTube, it would be stored in the cookies and would be sent back via a POST request as soon as you change the color mode. After that when you perform a consequent GET request to the YouTube server, it would return you the YouTube web page and the cookies populated with your preferences, this improves user experience as the user does not need to change the color mode on consequent visits to the particular website.
When you log into a website on a device, an encrypted unique token is stored in the cookie which keeps you logged in the website everytime you open the website.
Cookies are used to store the items in the shopping cart in an ecommerce website, they improve user experience as when you visit the website consequent times, you would not need to re-fill your cart with the items you had selected in the last session.

Web Security

You(as a developer) should never store sensitive information, like login information, in cookies as a hacker can perform XSS attacks or Session hijacking at1tacks to retrieve the cookies, which would cause loss of privacy of the sensitive information.
If a hacker steals your cookie on a specific website via some attack(like XSS), the attacked can use your cookie to pretend to be you on that specific website and he might do harm to your privacy.

Cookie Tracking

Cookie tracking is performed by third-party cookies usually, tracking cookies are used by third-parties to monitor the user's Web surfing habits and use the data for marketing purposes, like Google and Facebook ads. These types of cookies are generally considered as an invasion of privacy. When third-party ads are placed on a website, the third-party ad providers are also storing the user's data in cookies and then using the data for marketing and advertising purposes. For example: Big Tech giants, like google and facebook, store your data via cookies through ads as you surf the internet and then use that data to show you related advertisments, thus increasing their profits. Because of t4e privacy invasion of the users due to cookies, the EU(European Union) introduced the cookie law. The cookie law states that the websites need to ask for the user's permission to use cookies and give them a chance to opt out, thats why most of the websites ask for the user's permission before storing cookies.

In very rare cases, some ads might also access your camera if you allow to, or access it directly if you have allowed the main website to access your webcam. The advertising companies would then capture your facial expressions while watching a video add and determine whether you were happy or sad while watching it and then use the data for marketing. This can happen in very rare cases, research on this type of technology is being done at MIT Media Labs.

Personal Opinion

Users should be given the right to opt in for first-party cookies and just opt out for the third-party ones, but this gets very complex(from a developer perspective) and also it is very difficult to present to the user.

Cryptanalysis- the study of breaking cryptosystems explained

Hargunbeer Singh — Sat, 28 Aug 2021 12:32:42 +0000

Introduction

Cryptanalysis is a branch of cryptography that deals studies how to break codes and cryptosystems. It creates techniques to break the ciphers, the techniques are a lot more advanced than a simple brute force attack. Modern methods to break ciphers include linear cryptanalysis and differentil cryptanalysis, which are a lot more advanced than the traditional methods of breaking ciphers, like frequency analysis and index of coincidence. Cryptanalysis also includes exploiting weaknesses in the implementation of cryptography, these type of exploits are called side-channel attacks. People who study cryptanalysis are called cryptanalysts.

Methods of Cryptanalysis

Frequecy Analysis

Index of coincidence

Coincidence counting is a technique related to cryptography. The index of coincidence provides a probability of how likely is it to draw two matching letters by randomly selecting two letters from a given text. The probability of index of coincidence of a specific letter in a text is fully dependent on the number of times that specific letter appears in the string and it also depends on the length of the string the letter is withdrawn from. The probability of index of coincidence is 0.032(3.2%) in completely random text, it is 0.067(6.7%) for English and 0.072(7.2%) for German. The index of coincidence is (number of times that letter appears/ length of the text).

Applications

The index of coincidence is useful in the analysis of natural-language plaintext and the analysis of ciphertext. The coincidences in ciphertext can be caused by coincidences in the plaintext. So when coincidences in ciphertext are found, coincidences in the plaintext are also found at the same letter positions. This technique can be used to cryptanalyze the Vigenère cipher.

Index of coincidence can help determine when two texts are written in the same language using the same alphabet. This technique was used to examine the Bible code.

Linear Cryptanalysis

Linear cryptanalysis is a method of breaking block and stream ciphers. It is one of the two most widely used attacks on block ciphers. It is a plaintext attack. In Linear Cryptanalysis, the attacker studies the probabilistic linear relations(called linear approximations) between parity bits(bit added to a string of binary code, in the case of DES, the parity bit was added to the binary code to check if the key was indeed correctly retrieved, it was also to check whether during transmission, the wrong keys were used. These bits were used for error detection) of plaintext, the ciphertext and the secret key.

Differential Cryptanalysis

Differential cryptanalyis is a method of breaking ciphers. It is primary applicable to block ciphers, but it is also able to break stream ciphers and cryptographic hash functions. It is the study of how differences in the information inputted can affect the output resulting in a different output than common outputs. In the case of a block cipher, it is a set of techniques for tracing the differences through the network of transformation, and finding where the cipher exhibits non-common behaviour and exploiting such properties of the cipher to recover the cryptographic key.

DEV Community: Hargunbeer Singh

How do structs work internally?

Table of Contents

Introduction

Memory alignment

Structure Padding

Aligned structs

Advantages

Bibiliography

Remainder VS Modulus

Introduction

Overview

The Negative Number Game

Which is Which

Where can this knowledge be used

Relational DBMS explained

How YouTube optimizes video delivery

Introduction

Overview

Conclusion

Programming languages are overrated!

Data Structures for Dummies

Introduction

Types of Data Structure

Array

Strings

Matrix

Struct

Node and Linked List

Queues

Stacks

Trees

Graph

Others

Conclusion

Cryptographic frequency Analysis explained

Cryptography explained

Introduction

Overview

Terminology

Disciplines

Read More

Clickjacking explained

Introduction

Example

Categories

Classic

Likejacking

Nested

Cursorjacking

MouseJack

Browserless

CookieJacking

FileJacking

Password manager attack

Preventive Measures

Client-Side

Sever-side

Framekiller

X-Frame-Options

Content-Security-Policy

Links

Cross Site Request Forgery Explained

Introduction

Overview

Examples

Preventive Measures

'Referrer' Header

One-time key

Same-Origin Policy

Synchronizer token pattern

CSRF Phishing attack

🍪Cookies and Cookie Tracking Explained

Introduction

Examples

Web Security

Cookie Tracking

Personal Opinion

Cryptanalysis- the study of breaking cryptosystems explained

Introduction