Techniques for verifying message authenticity is provided. In some implementations, a verification request to verify authenticity of a first message is received from a user computing device. The verification request includes a first user identifier and verification information. A delivery message record is obtained. The delivery message record includes a plurality of entries associated with one or more messages sent to one or more user computing devices. Each entry includes a user identifier and feature information of a respective message of the one or more messages. At least one entry that has a second user identifier matching the first user identifier is identified. In response to determining that the feature information of the identified at least one entry matches the verification information from the verification request, a verification message is provided to the user computing device. The verification message indicates that authenticity of the first message is verified.