A Mathematical Introduction to Logic: How Logic Provides a Foundation for Hacking

Profile image for programmere
October 13, 2016 | Views: 5058

Begin Learning Cyber Security for FREE Now!

FREE REGISTRATIONAlready a Member Login Here

Like any other profession, hacking has both practical and theoretical applications. Most of the Open topics deal with the practical side of hacking, so I thought I could help balance that a little by talking about the theoretical side of hacking.

I am going to vastly simplify the material in my third year mathematics course “A mathematical introduction to logic” so that those with little to no mathematical aptitude can follow along. If you wish to read more on the subject, you can always get the book cited in my bibliography.

Today I’d like to focus on the topic of deductive proofs. That is, I would like to look at getting from a set of hypothesis (i.e. assumptions), a set of tautologies (i.e. always true statements), and the use of Modus Ponens (If P is true, and P implies Q, then Q), we can reach a conclusion.

Here’s a practical example of a informal proof:

Assume the following two statements which are both a hypothesis:

A = “If port 22 is open then the computer is running SSH”

B = “The computer is not running SSH”

And the following tautology:

C=”If Y implies Z, then not Z implies not Y” [p.s. this is called the contrapositive, and is provably a tautology]

Can we prove the following?

D = “Port 22 is closed”

The answer is yes. Let me explain the proof informally:

If we apply our tautology C to A (through Modus Ponus), we get the statement E = “If the computer is not running SSH, then port 22 is closed.” We then use Modus Ponens with B being true and E = B implying D to get that D is true.

What we did above is the essence of deductive proofs. The rest of this article will be devoted to recreating the above proof in the context in mathematics.

Describing a formal language requires three pieces of of information:

  1. A set of symbols. For our purposes we will only consider 0-order logic. Don’t worry if you do not understand the next sentence as I will cover these in more detail below.  These consist of the left parenthesis, the right parenthesis, the negation symbol, the and symbol, the  or symbol, the if then symbol, the if and only if symbol, and a countably infinite set of sentence symbols.
  2. rules for “grammatically correct” finite sequences of symbols (i.e. (((1 + 3) + 1) = 5) is grammatically correct in common mathematics where )+(1(31+)()= is not.)
  3. Allowable translations between English and Logic

(Enderton, 1972, p. 12-13)

Before we look at grammar, let’s look at the atoms of our 0-order logic:

  1. The left parenthesis (‘(‘), and the right parenthesis (‘)’) are used for the order of operations. We first evaluate expressions inside brackets before we evaluate anything after brackets.
  2. The ‘not’ operator has only one parameter, and returns the opposite of the parameter.
  3. The ‘and’ operator has two parameters and returns true if both of it’s parameters are true.
  4. The ‘or’ operator has two parameters and returns true if one of it’s parameters are true or both of it’s parameters are true
  5. The ‘if then’ operator has two parameters and returns true if  the first parameter is false or the second parameter is true or both.
  6. The ‘if and only if’ operator has two parameters and returns true if both of it’s parameters are false or both of it’s parameters are true
  7. The sentence symbols, unlike the rest of the symbols are subject to change from one context to the other. These are true of false statements

(Enderton, 1972, p. 14)

The grammar for our 0-order logic (henceforth known as a well formed formula)  will be built from the following rules:

  1. Every sentence symbol is a well formed formula
  2. If a and b are well formed formula’s, so are ‘(not a)’, ‘(not b)’, ‘(a and b)’, ‘(a or b)’, ‘(if a then b)’, ‘(a if and only if b)’
  3. No expression is a well formed formula unless it is compelled by 1. or 2.

(Enderton, 1972, p. 16)

I could go on and create a 10 part series where I explain 0-order logic in depth (let me know if you want that), but this is a hacking forum and not a mathematics forum. Let me just skip to the point and use the extreamly limited tools we have to make a proof:

A = “Port 22 is running”

B = “SSH is running”

Then we can construct a proof. Justification is as follows. H is a hypothesis, T is a Tautology, and (i, j; MP) is Modus Ponus applying to the ith and jth components.

<(If A then B), (not B), (If (If Y then Z) then (If (not  Z) then (not Y))), If (not B) then (not A), not(A)>

Justifications: <H, H, T, (1, 3; MP), (2, 4; MP)>

So, what is the point of the mathematical proofs? After all, we were able to explain the proof in English, do why take the time to translate to logic? Here are three reasons we would want to do that:

  1. Reduction of ambiguity: most modern everyday languages are powerful because there are many ways to express the same statement. In formal logic, we cannot have any two sentence symbols be reducible to a combination of the other sentence symbols
  2. Justification: While informal proofs can be correct, often steps will be omitted or  tautologies assumed without justification. Using a formal system exposes hidden assumptions and allows us to make sure that our conclusion follows from our premises
  3. Reduction of words: While this article was written in English, the mathematical equivalent takes much less space to express and therefore much more complex proofs can be expressed without losing sight of the bigger picture.

The next time you want to prove a computer is secure, don’t just run your suite of tools on it, but try to prove it rigorously.

If you have any suggestions on what you would like me to post next, please comment on this article.

If you liked my article and would like to read another one posted by me, visit https://www.cybrary.it/0p3n/tailgating-following-someone-into-a-building-101/ . I promise it will be more practical.

Bibliography:

Enderton, H. B. (1972). A mathematical introduction to logic (2nd ed.). New York: Academic Press.

Regards,

ProgrammerE

Share and Earn Cybytes
FacebookTwitterGoogle+LinkedInEmail
Save
+1
14
8
Use Cybytes and
Tip the Author!
Join
Share and Earn
Cybytes
FacebookTwitterGoogle+LinkedInEmail
Ready to share your knowledge and expertise?
Be the Best at Whatever You Do.
We Have the Tools to Get You There.
Visit the NEW Marketplace of Over 500 Skill Enhancement Tools.
8 Comments
  1. nice post sir..
    but according to my in knowledge Mathematical tricks we used only make our logic for hacking purpose. create own logic for hacking
    like this we can searching our victim and check its vulnerability..
    thanks.

    • Mr. Ajeet0302

      Thank you for reading my post. I’m having trouble understanding your comment. I’m going to do my best to interpret it below but please respond if my rephrasing of your comment is incorrect.

      Nice post sir.
      According to my knowledge in mathematical tricks we only used or made up our logic for hacking purpose. If you create your own logic for hacking like the above then with permission from senior management we can search our target’s machines and check for vulnerabilities.
      Thank you for sharing. (AJEET0302, 2017)

      Although you seem to be on the right track practically to do penetration testing, I feel like you’ve missed the point of this article. Let me put it to you this way: Imagine if instead of learning the five stages of penetration testing and the goals of each phase you only learned the tools of the trade. Don’t get me wrong, the tools of the trade (Metaspoit, Wireshark, Burp Suite, etc.) are important but as the times and technologies change the programs change with them. Just ask any Fortran/Cobol programmer. Having a larger view of what your studying helps you quickly adapt to whatever comes next. Mathematical logic is the basis for all mathematics, including linear algebra which is the basis for computers. Whatever logic you create using mathematical tricks should be traceable back to mathematical logic and/or set theory. Shortcuts are nice but are often abused as people make logical fallacies. For example, say that some of our staff are hackers and some hackers are criminal hackers. It does not follow that some of our staff are criminal hackers. In statistics, we would write it P(A and B) = P(A)P(B|A) (the probability of some of our staff being criminal hackers is the probability of our staff being hackers (which is 1, or certain) times the probability that given a hacker is part of our staff they are a criminal hacker)

      The point is, theory is extremely important. Additionally, if your going to be working in penetration testing or likewise field, do your best to change the public perception of hacking. While there are victim machines, do your best to use lighter language or specify that you require write off.

      Thanks once again for your comment, I know I can be a little blunt. I hope you take my advice to heart and become a wonderful member of this community

      Regards,

      ProgrammerE

  2. Two of my favorite things, logic and maths. Thanks for the share!

  3. I think you are using Modus tollens, not ponens – but it has been a while since my logic class. Thanks for the quick refresher!
    (Modus ponens) A -> B, A ∴ B
    A: if you do your homework, you get a lollipop.
    B: you did your homework.
    Therefore C: you get a lollipop.
    (Modus tollens) A -> B, -B ∴ -A
    A: if you do your homework, you get a lollipop.
    B: you did NOT get a lollipop.
    Therefore C: you did NOT do your homework.

    In the more practical sense, many programs allow you to set the port used. Is it possible someone could mis-configure their non-SSH application to run on port 22?

    • Mr. Smith

      Regarding your first point, had I not specifically defined C and applied C to A, you would be right. However, because we only allow Modus Ponens in formal mathematical logic (Although many people site Modus Tollens as an informal step), I specifically had placed the contrapositive as a tautology so I can site it directly. In step four of my proof, I take the literal “(If (If Y then Z) then (If (not Z) then (not Y)))” and apply it letting Y = A, and Z = B.

      In the more practical sense, it is 100% possible that someone could mis-configure their non-SSH application to run on port 22. It is also possible to run SSH on another port besides port 22. This is an excellent opportunity to talk about the difference between validity and soundness. Logic is about obtaining validity. A mathematical proof is valid if when all of the hypothesis are true then the conclusion is true. A mathematical proof is sound if the mathematical proof is valid and the hypothesis are true then the conclusion is also true. The proof I provide as an example above is valid but may not be sound. One is a matter of mathematical logic, and one is a matter of running nmap.

      That being said, you clearly have a good grasp on logic. Both arguments were good arguments and I wish you the best in all of your studies.

  4. Profile image for rasteril

    Hey, very interesting post!
    I’m curious to find out more about the theoretical side of hacking. Do you have any pointers as to where I should look?
    Mathematics and hands on Computer Security, I love them both. That’s why I’m looking for a neat combination.
    Thanks and keep posting!
    Cheers

    • To a fellow hacker and numberphile, RAQ14M

      I have a lot of difficulty tailoring some good resources to you because of your current lack of information provided in the post or on your profile. If you are just learning programming (perhaps with a programming language like Turing), a complex and in depth resource will only serve to confuse you and diminish your interest in the subject. Likewise, if you are doing your masters in mathematics and I provide an introductory resource it would be of no use to you and you would end up more frustrated for a lack of in depth resources. Therefore, I am going to tier my resources into three levels: Introductory, Mainstream and Advanced. If you know what the dot product or cross product between two vectors is, you may skip directly to Mainstream. If you know what I mean by an idempotent function is a vector space over a field, than you can skip directly to Advanced

      Introductory:
      The Complete Idiot’s Guide to Algebra (or equivalent secondary linear algebra book)
      Calculus Demystified (or equivalent secondary calculus book)
      Logic For Dummies (or equivalent secondary logic book)

      Mainstream:
      Gilbert/Gilbert: Linear Algebra and Matrix Theory (Or equivalent undergrad calculus textbook)
      Marsden & Tromba, Vector Calculus (Or equivalent undergrad calculus textbook)
      Enderton, H. B. (1972). A mathematical introduction to logic (as seen referenced above)

      Advanced:
      Elementary Number Theory, Charles Vanden Eynden, Waveland Press (or equivalent number theory course)
      Introduction to Cryptography with Coding Theory, Wade Trappe; Lawrence C. Washington, Pearson (Or equivalent mathematical cryptography course)
      Introduction to Computer and Network Security, Richard R. Brooks (or equivalent hacking course)

      I hope the resources above help you on your way to learning what you want to become what you want.

      Cheers

      ProgrammerE

  5. I found logic as confusing so hacking is.Anyway Thanks

Comment on This

You must be logged in to post a comment.

Our Revolution

We believe Cyber Security training should be free, for everyone, FOREVER. Everyone, everywhere, deserves the OPPORTUNITY to learn, begin and grow a career in this fascinating field. Therefore, Cybrary is a free community where people, companies and training come together to give everyone the ability to collaborate in an open source way that is revolutionizing the cyber security educational experience.

Cybrary On The Go

Get the Cybrary app for Android for online and offline viewing of our lessons.

Get it on Google Play
 

Support Cybrary

Donate Here to Get This Month's Donor Badge

 

Cybrary|0P3N

A “Noob’s” Guide to Ransomware
Views: 515 / September 23, 2017
Dark Network Guide!
Views: 2165 / September 22, 2017
UNM4SK3D: SEC, APT33, and CCleaner
Views: 970 / September 22, 2017
Penetration Testing Flash Applications
Views: 1082 / September 22, 2017
d
Skip to toolbar
Cybrary works best if you switch to our Android-friendly app
Continue

We recommend always using caution when following any link

Are you sure you want to continue?

Continue
Cancel