Hash Function Ontology

FLOW ALGEBRA
TITLE: Hash Function Ontology
DOMAIN: Discrete Mathematics / Cryptography
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/cryptography/hash-function-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORS: Mark Higgins — Sky (Recursive AI)
SOURCE_STATUS: Mathematical synthesis; live page not independently verified.

1. ONTOLOGY
ontology HashFunctionOntology {
  entity Message: BitString
  entity Digest: BitString
  entity HashFunction: Function(BitString, BitString)
  entity CryptographicHash: HashFunction
  entity Collision: Pair(Message, Message)
  entity DomainSeparator: BitString
  entity SecurityParameter: NaturalNumber
  entity Adversary: ProbabilisticAlgorithm
  entity HashAlgorithm: Specification
  entity HashInstance: AlgorithmImplementation
}

2. TYPED DEFINITIONS
  H: {0,1}* -> {0,1}^n, where n >= 1 is a fixed digest length.
  digest(H,m) := H(m).
  collision(H,m1,m2) := (m1 != m2) AND (H(m1) = H(m2)).
  second_preimage(H,m,m2) := (m != m2) AND (H(m) = H(m2)).
  preimage(H,y,m) := H(m) = y.
  NOTE: A general-purpose noncryptographic hash need not satisfy cryptographic security properties.

3. RELATIONSHIPS
  HashFunction --maps--> Message TO Digest
  CryptographicHash --subtype_of--> HashFunction
  Collision --requires--> DistinctMessages
  Collision --shares--> EqualDigest
  CryptographicHash --used_by--> DigitalSignature
  CryptographicHash --used_by--> DataIntegrityCheck
  CryptographicHash --used_by--> CommitmentScheme
  CryptographicHash --used_by--> MerkleTree
  CryptographicHash --used_by--> KeyDerivationConstruction
  HashAlgorithm --implemented_by--> HashInstance

4. OPERATIONS
  HASH(H,m) -> Digest
  VERIFY_DIGEST(H,m,d) -> Boolean := constant_time_equal(H(m),d)
  DETECT_COLLISION(H,m1,m2) -> Boolean := m1 != m2 AND H(m1) = H(m2)
  DOMAIN_SEPARATED_HASH(H,tag,m) := H(ENCODE_LENGTH(tag) || tag || m)
  NOTE: Domain separation encoding must be unambiguous and protocol-specific.

5. SECURITY PROPERTIES
  PREIMAGE_RESISTANCE: Given digest y sampled from an appropriate hash-output distribution, finding m with H(m)=y is computationally infeasible.
  SECOND_PREIMAGE_RESISTANCE: Given m, finding m2 != m with H(m2)=H(m) is computationally infeasible.
  COLLISION_RESISTANCE: Finding any m1 != m2 with H(m1)=H(m2) is computationally infeasible.
  DETERMINISM: For fixed H and m, repeated evaluation yields the same digest.
  NOTE: These are computational assumptions and threat-model-dependent claims, not mathematical guarantees.
  NOTE: Digest equality alone does not authenticate origin or establish integrity against an adversary able to replace both message and digest.

6. ALGEBRAIC AND INFORMATION PROPERTIES
  DETERMINISM: H(m) = H(m).
  FINITE_RANGE: |{0,1}^n| = 2^n.
  PIGEONHOLE: Because {0,1}* is infinite and the range is finite, collisions necessarily exist.
  IDEAL_BIRTHDAY_BOUND: Generic collision search against an ideal n-bit hash takes approximately O(2^(n/2)) evaluations.
  IDEAL_PREIMAGE_BOUND: Generic preimage search takes approximately O(2^n) evaluations.
  NOTE: Ideal bounds are heuristics/models and may not describe attacks against a specific construction.
  NON_INVERTIBILITY: Cryptographic hash functions are not encryption and have no decryption key.

7. INFERENCE RULES
  IF m1 != m2 AND H(m1) = H(m2) THEN collision(H,m1,m2).
  IF collision(H,m1,m2) THEN collision_resistance_counterexample(H,m1,m2).
  IF H(m) != expected_digest THEN integrity_check_failed(m).
  IF H(m) = expected_digest THEN digest_matches(m), NOT authenticated_source(m).
  IF algorithm_is_obsolete(H) THEN require_security_review(H).

8. VALIDATION
  CHECK output_length(H(m)) = n.
  CHECK repeatability(H,m): H(m) == H(m).
  CHECK standard_test_vectors(H) match published specification.
  CHECK byte_encoding(m) is explicitly specified.
  CHECK domain_separation_tags are unique within the protocol.
  CHECK cryptographic_algorithm_choice meets current deployment policy.
  CHECK implementation uses vetted library and appropriate side-channel protections.
  NEGATIVE_TEST: Distinct messages can theoretically have identical digests; never assert collision impossibility.
  NEGATIVE_TEST: Password storage requires a dedicated password-hashing/KDF scheme with salts and appropriate cost, not a fast raw hash.

9. SEMANTIC_EQUIVALENCE
  "message digest" ~= "hash output" (context: cryptographic hashing).
  "collision resistance" != "collision freedom".
  "hashing" != "encryption".
  "checksum" != "cryptographic authentication".
  "preimage resistance" != "second-preimage resistance".
  "SHA-256" instance_of CryptographicHashAlgorithm.

10. CONFIDENCE
  definitions: 0.99 (standard mathematical definitions)
  security_claims: CONDITIONAL (algorithm, adversary model, security parameter and implementation)
  page_alignment: UNVERIFIED
  source_provenance: established cryptographic theory; source URL supplied by user

11. FLOW_HASH
  canonicalisation: UTF-8, normalise line endings to LF, hash canonical content excluding the FLOW_HASH output field.
  digest_algorithm: SHA-256
  digest_value: COMPUTE_ON_PUBLICATION
  NOTE: No uncomputed or fabricated digest is asserted.

12. UPDATE_MODEL
  trigger: new cryptanalysis, algorithm deprecation, standard revision, implementation vulnerability, ontology revision.
  steps: review -> update typed entities/rules -> rerun validation -> recompute FLOW_HASH -> publish version with provenance.
  compatibility: retain stable identifiers where semantics are unchanged.

13. AI_CONSUMPTION
  ingest_mode: typed ontology + inference rules + validation constraints
  use_cases: knowledge graphs, cryptographic concept classification, protocol modelling, security education, semantic retrieval
  safeguards: distinguish proven algebraic properties from computational security assumptions; do not treat hash equality as authentication.
  output_contract: {concept, definition, inputs, outputs, relationships, security_assumptions, validation_status, provenance, confidence}

END FLOW ALGEBRA