EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 600+ Courses All in One Bundle
  • Login

Brute Force Algorithm

By Priya PedamkarPriya Pedamkar

Home » Software Development » Software Development Tutorials » Network Security Tutorial » Brute Force Algorithm

Brute Force Algorithm

Introduction to Brute Force Algorithm

“Data is the new oil” this is the new mantra that is ruling the global economy. We live in the digital world, and every business revolves around data, which translates into profits and helps the industries stay ahead of their competition. With the rapid digitization, an exponential increase in the app-based business model, cyber-crimes is a constant threat. One such common activity that hackers perform is Brute force.

Brute Force is a trial and error approach where attackers use programs to try out various combinations to break into any websites or systems. They use automated software to repetitively generate the User id and passwords combinations until it eventually generates the right combination.

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

Brute-Force Search

Brute force search is the most common search algorithm as it does not require any domain knowledge; all that is required is a state description, legal operators, the initial state and the description of a goal state. It does not improve the performance and completely relies on the computing power to try out possible combinations.

The brute force algorithm searches all the positions in the text between 0 and n-m, whether the occurrence of the pattern starts there or not. After each attempt, it shifts the pattern to the right by exactly 1 position. The time complexity of this algorithm is O(m*n). If we are searching for n characters in a string of m characters, then it will take n*m tries.

Let’s see a classic example of a travelling salesman to understand the algorithm in an easy manner.

Suppose a salesman needs to travel 10 different cities in a country, and he wants to determine the shortest possible routes out of all the possible combinations. Here brute force algorithm simply calculates the distance between all the cities and selects the shortest one.

Popular Course in this category
Cyber Security Training (12 Courses, 3 Projects)12 Online Courses | 3 Hands-on Projects | 77+ Hours | Verifiable Certificate of Completion | Lifetime Access
4.5 (6,002 ratings)
Course Price

View Course

Related Courses
CDN Training (2 Courses)OSPF Training Program (2 Courses)Penetration Testing Training Program (2 Courses)

Another example is to make an attempt to break the 5 digit password; then brute force may take up to 105 attempts to crack the code.

Brute Force Sort

In the brute force sort technique, the data list is scanned multiple times to find the smallest element in the list. After each iteration over the list, it replaces the smallest element to the top of the stack and starts the next iteration from the second smallest data in the list.

The above statement can be written in pseudo-code as follows.

 brute force algorithm 1

 

 

 

Here the problem is of size ‘n’, and the basic operation is ‘if’ test where the data items are being compared in each iteration. The will be no difference between the worst and best case as the no of swap is always n-1.

Brute Force String Matching

If all the characters in the pattern are unique, then Brute force string matching can be applied with the complexity of Big O(n) where n is the string’s length. Brute force String matching compares the pattern with the substring of a text character by character until it gets a mismatched character. As soon as a mismatch is found, the substring’s remaining character is dropped, and the algorithm moves to the next substring.

The below pseudo-codes explain the string matching logic. Here the algorithm is trying to search for a pattern of P[0…m-1] in the text T[0….n-1].

Here the worst case would be when a shift to another substring is not made until MTh comparison.

 brute force algorithm 2

Closest Pair

Problem statement: To find out the two closest points in a set of n points in the two-dimensional cartesian plane. There is n number of scenarios where this problem arises. A real-life example would be in an air traffic control system where you have to monitor the planes flying near to each other, and you have to find out the safest minimum distance these planes should maintain.

Image - 3

Source Link: Wikipedia

The brute force algorithm computes the distance between every distinct set of points and returns the point’s indexes for which the distance is the smallest.

Brute force solves this problem with the time complexity of [O(n2)] where n is the number of points.

Below the pseudo-code uses the brute force algorithm to find the closest point.

brute force algorithm 4

Convex Hull

Problem Statement: A convex hull is the smallest polygon that contains all the points. The convex hull of a set s of the point is the smallest convex polygon containing s.

image 5

The convex hull for this set of points is the convex polygon with vertices at P1, P5, P6, P7, P3.

A line segment P1 and Pn of a set of n points is a part of the convex hull if and only if all the other points of the set lies inside the polygon boundary formed by the line segment.

Let’s relate it with the rubber band,

Point (x1, y1), (x2,y2) make the line ax+by = c

When a = y2-y1, b = x2-x1 and c = x1*y2 – x2*y1 and divides the plane by ax+by-c < 0 and ax+by-c > 0

So we need to check ax+by-c for the other points.

Brute force solve this problem with the time complexity of O(n3)

Exhaustive Search

For discrete problems in which there is no known efficient solution, it becomes necessary to test each and every possible solution sequentially.

Exhaustive search is an activity to find out all the possible solutions to a problem in a systematic manner.

Let’s try to solve the Travelling salesman problem (TSP) using a Brute exhaustive search algorithm.

Problem Statement: There are n cities that salesmen need to travel, he wants to find out the shortest route covering all the cities.

We are considering Hamilton Circuit to solve this problem. If a circuit exists, then any point can start vertices and end vertices. Once the start vertices are selected, then we only need the order for the remaining vertices, i.e. n-1

Then there would be (n-1)! Possible combinations and the total cost for calculating the path would be O(n). thus the total time complexity would be O(n!).

Conclusion

Now that we have reached the end of this tutorial, I hope you guys have now got a fair idea of what Brute Force is. We have also seen the various Brute force algorithm that you can apply in your application.

Recommended Articles

This has been a guide to Brute Force Algorithm. Here we discussed the Basic concepts of the Brute Force Algorithm. You can also go through our other suggested articles to learn more –

  1. What is an Algorithm?
  2. Algorithm Interview Questions
  3. Introduction To Algorithm
  4. Algorithm in Programming

Cyber Security Training (12 Courses, 3 Projects)

12 Online Courses

3 Hands-on Projects

77+ Hours

Verifiable Certificate of Completion

Lifetime Access

Learn More

1 Shares
Share
Tweet
Share
Primary Sidebar
Network Security Tutorial
  • Algorithm
    • IDEA Algorithm
    • MD5 Algorithm
    • Symmetric Algorithms
    • Diffie Hellman Key Exchange Algorithm
    • Digital Signature Algorithm
    • Encryption Algorithm
    • Advanced Encryption Standard
    • Asymmetric Encryption
    • ElGamal Encryption
    • HMAC
    • DES Algorithm
    • Brute Force Algorithm
    • SHA Algorithm
    • RSA Algorithm
    • What is Digital Certificate?
    • Certificate Revocation
    • RC5
  • Basics
    • Security Consultant Definition
    • Security Policies
    • What is Network Security
    • What is Data Security?
    • What is Cryptography
    • Cryptography Techniques
    • Cryptography Tools
    • Data Security Techniques and Privacy
    • Digital Signature Cryptography
    • Java Cryptography
    • Basics of Cybersecurity
    • What is Network Topology
    • Algorithms and Cryptography
    • HTTP Methods
    • Security Technologies
    • Security Architecture
    • Network Topologies
    • What is a Physical Address?
    • Logical Address
    • What is Storage Area Network?
    • Mobile Ad Hoc Network
    • What is Computer Networks?
    • Security Principles
    • What is Remote Access?
  • Protocols
    • What is TCP Protocol
    • What is TCP/IP
    • How do IP Addresses Work?
    • Routing Protocols Types
    • What is Telnet
    • What is TFTP
    • What is DHCP
    • What is SFTP
    • Address Resolution Protocol
    • Internet Control Message Protocol
    • Simple Mail Transfer Protocol
    • Internet Security Protocols
    • SMTP Protocol
    • Types of Networking Protocols
    • User Datagram Protocol
    • Data Link Layer
    • Data Link Layer Services
    • Network Layer
    • Transport Layer Protocols
    • What Is Networking Protocols
    • TFTP
    • What is ARP
    • Basic Fundamental Of Networking
    • What is IPv4
    • What is IPv6
    • CIFS Protocol
    • What is SMB?
    • What is EIGRP
    • What is LLDP?
  • Routing
    • What is Router
    • Types of Routers
    • Dynamic Routing
    • Routing Algorithms
    • Routing Protocol
    • What is Routing
    • What is Static Routing
    • Important Types of DNS Servers (Powerful)
  • Attacks
    • Types of Network Attacks
    • What is Trojan Horse Virus
    • What is DOS
    • Types of DOS Attacks
    • DDos Attack Mitigation
    • Ransomware Attack  
    • Types of Cyber Attack
    • What is a Brute Force Attack
    • What is a Phishing Attack
    • What is Cyber Attack
    • What is DDoS Attack
    • What is Man In The Middle Attack
    • What is Man In The Middle Attack
    • What is Ransomware
    • What is Pharming
    • What is Phishing
    • What is CSRF
    • DNS Amplification Attack
    • Denial of Service Attack
  • Encryption/ Decryption
    • Encryption process
    • Public Key Encryption
    • Symmetric Key Encryption
    • What is Encryption
    • What is Decryption
    • Types of Cipher
    • Transposition Techniques
    • What is Steganography
    • One Time Pad
    • Steganography Techniques
  • Hosting
    • Types of Web Hosting
    • Free Web Hosting Sites
    • What is Hosting
    • What is VPS Hosting
    • What is Web Hosting
    • Types of Domain
    • VPN Applications for PC
    • Why we use VPN?
    • What is Virtual Host?
  • Firewalls
    • What is a Firewall?
    • Types of Firewalls
    • Firewall Devices
    • Firewall Uses
  • Advanced
    • Cryptosystems
    • Configuring DHCP Server
    • Block Cipher modes of Operation
    • TCP/IP Model
    • Types of Network
    • Types of Network Devices
    • Types of Network Topology
    • Types of Intrusion Prevention System
    • Types of Proxy Servers
    • Types of Websites
    • Types of NAT 
    • Mobile IP
    • Career in Automobile Design
    • What is TFS
    • What is NAT
    • What is OSI Model
    • Data Link Layer OSI Model
    • What is Cross Site Scripting
    • Applications of Sensors
    • ARP Packet Format
    • Asymmetric Information
    • Autoencoders
    • What is FTP Server?
    • IPS Tools
    • IPv4 Header Format
    • IPv6 Header Format
    • Authentication Header
    • Kerberos
    • Network Mapper
    • Network Scanning Tools
    • Network Mapping Tools
    • Network Access Control
    • Vulnerability Assessment Tools
    • Network Sniffer
    • Networking Commands
    • Networking Devices
    • Networking Strategies
    • Digital Certificate
    • What is a Digital Signature?
    • Digital Signature Softwares
    • Digital Signature Types
    • Digital Signature vs Digital Certificate
    • PKCS
    • What is FTP
    • FTP Commands
    • What is MIME?
    • What is Smart Card?
    • Networking Ports
    • Mutual Authentication
    • Password Authentication
    • Data Masking 
    • Authentication Tokens
    • Biometric Authentication
    • What is IP?
    • IPSec
    • Secure Electronic Transaction
    • What is CIDR
    • Static Binding and Dynamic Binding
    • What is SSL
    • PKIX
    • Public Key Infrastructure
    • What is Wireshark
    • Daisy Chain Topology
    • Markov Logic Network
    • Security engineering
    • SNMP Monitoring Tools
    • Network Analysis Tools
    • Server Monitoring Tools
    • Network Discovery Tools
    • Network Management Tool
    • SIEM Tools
    • OSINT Tools
    • Multiple Ping Tool
  • Interview Questions
    • Network Security Interview Questions
    • Networking Interview Questions
    • EIGRP Interview Questions

Related Courses

CDN Training

OSPF Certification Training

Penetration Training Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Java Tutorials
  • Python Tutorials
  • All Tutorials
Certification Courses
  • All Courses
  • Software Development Course - All in One Bundle
  • Become a Python Developer
  • Java Course
  • Become a Selenium Automation Tester
  • Become an IoT Developer
  • ASP.NET Course
  • VB.NET Course
  • PHP Course

© 2020 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA Login

Forgot Password?

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

Special Offer - Cyber Security Training (12 Courses, 3 Projects) Learn More